건전한 건전지
article thumbnail
728x90
반응형

https://www.acmicpc.net/problem/2134

 

2134번: 창고 이전

첫째 줄에 세 정수 n, m, k가 주어진다. 다음 줄에는 n개의 정수로 기존 창고의 각 층에 보관되어 있는 물품의 개수가 1층부터 n층의 순서로 한 줄에 하나씩 주어진다. 다음 m개의 줄에는 창고의 각

www.acmicpc.net

 

 

 

- 생각한 내용 -

물건은 1회 이동당 1개씩만 챙겨서 새로운 창고로 이동함.

높은 층에 있는 물건을 옮길수록 Total Cost가 늘어남 -> 최대한 많은 물건을 옮기는 것이 목적 -> 새로운 창고의 1층부터 채우고, 기존 창고의 1층 물건부터 옮기면 최소 Cost로 작업 가능

인부의 수는 생각할 필요가 없음. -> 인부의 수는 결과에 영향을 주지 않음 (빨리 끝내거나 효율적으로 하는게 아님)

 

- 구현 방법 -

반복문 한 번당 1개의 물건을 옮길 것임.

원래 창고의 물건이 다 떨어지거나, 새로운 창고의 공간이 꽉 찬다면 즉시 종료시킨다.

창고의 각 층을 배열로 생각하고 만들어 해당 배열이 0이 된다면 (== 해당 층의 물건 or 공간) 포인터를 배열로 이동시킨다.

 

<cpp />
long long n, m, k; cin >> n >> m >> k; vector <long long> originStorage; vector <long long> newStorage; // 총 비용을 저장하는 변수 long long totalCost = 0; // 창고의 남은 물건 수와 새로운 창고의 남은 공간을 알려주는 변수 long long originCnt = 0, newCnt = 0; for (long long i = 0; i < n; i++) { long long c; cin >> c; originStorage.push_back(c); originCnt += c; } for (long long i = 0; i < m; i++) { long long c; cin >> c; newStorage.push_back(c); newCnt += c; }

 

원래 창고와 새로운 창고의 물건을 입력받는 부분

옮겨야 하는 물건의 총 개수를 OriginCnt로 저장해놓고 새로운 창고의 총 저장공간을 newCnt로 저장해놓는다.

 

<cpp />
// 총 몇개의 물건을 옮겼는지 세는 변수 long long totalCnt = 0; long long originCurFloor = 0, newCurFloor = 0; while (originCnt && newCnt) { // 해당 층에 물건이 없으면 다음 층으로 if (!originStorage[originCurFloor]) { originCurFloor++; continue; } // 해당 층에 공간이 없으면 다음 층으로 if (!newStorage[newCurFloor]) { newCurFloor++; continue; } originStorage[originCurFloor]--; newStorage[newCurFloor]--; originCnt--; newCnt--; totalCost += originCurFloor + 2 + newCurFloor; totalCnt++; }

현재 각 창고의 어떤 층에서 물건을 옮겨서 적재하고 있는지 확인하기 위해 originCurFloor와 newCurFloor 변수를 준비한다. (높은 층일수록 높은 비용이 든다.)

 

원래 창고의 0번 층부터 물건을 한 개씩 빼서 새로운 창고의 0번 층에 쌓아준다.

-> originStorage[originCurFloor]--, newStorage[newCurFloor]--

옮겨야 하는 물건의 총 개수와 새로운 창고의 남은 공간 개수를 한 개씩 줄인다.

-> originCnt--, newCnt--;

totalCost를 증가시킨다. 배열은 0번부터 시작하므로 origin과 new 합쳐서 2를 증가시키면 된다.

-> totalCost += originCurFloor +2 + newCurFloor;

총 옮긴 물건의 수를 1개 증가 시킨다

-> totalCnt++

 

해당 층에 물건이 없거나 적재할 공간이 없다면 어떻게 될까?

originCurFloor나 newCurFloor를 1 증가시켜주고 continue를 통해 이번 반복문은 실행하지 않고 넘어간다.

-> 매 실행마다 originCnt(총 물건의 양)과 newCnt (총 적재가능 공간)을 빼주기 때문에 vector out of range는 발생하지 않음

 

 

1. 전체 코드

더보기

전체 코드

<cpp />
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); long long n, m, k; cin >> n >> m >> k; vector <long long> originStorage; vector <long long> newStorage; long long totalCost = 0; long long originCnt = 0, newCnt = 0; for (long long i = 0; i < n; i++) { long long c; cin >> c; originStorage.push_back(c); originCnt += c; } for (long long i = 0; i < m; i++) { long long c; cin >> c; newStorage.push_back(c); newCnt += c; } long long totalCnt = 0; long long originCurFloor = 0, newCurFloor = 0; while (originCnt && newCnt) { // 해당 층에 물건이 없으면 다음 층으로 if (!originStorage[originCurFloor]) { originCurFloor++; continue; } // 해당 층에 공간이 없으면 다음 층으로 if (!newStorage[newCurFloor]) { newCurFloor++; continue; } totalCnt++; totalCost += originCurFloor + 2 + newCurFloor; originStorage[originCurFloor]--; newStorage[newCurFloor]--; originCnt--; newCnt--; } cout << totalCnt << " " << totalCost; }
728x90
반응형
profile

건전한 건전지

@건전한 건전지

나는 언리얼의 왕이 될 남자다 👑