[백준/C++] 창고 이전 - 2134번 / CPP풀이

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

2134번: 창고 이전

 

 

 

- 생각한 내용 -

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

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

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

 

- 구현 방법 -

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

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

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

 

	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로 저장해놓는다.

 

	// 총 몇개의 물건을 옮겼는지 세는 변수
	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는 발생하지 않음

 

 

전체 코드

전체 코드

#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;

}