취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2134번 문제인 창고 이전이다.
문제는 아래 링크를 확인하자.

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

원래의 창고에 쌓여있던 짐의 개수를 total1, 옮겨갈 창고에 쌓아둘 수 있는 짐의 개수를 total2라고 할 때, 옮길 수 있는 짐의 최대 개수는 total = min(total1,total2)가 됨은 자명하다.

짐의 이동비용은 원래의 창고에서 옮겨갈 짐을 창고의 아래에서부터 total개를 골라 옮겨갈 창고에 아래부터 total개의 짐을 채워넣는 것이 항상 최소가 된다. 각 짐을 원래의 창고에서 밖으로 빼는 비용과 뺀 짐을 옮겨갈 창고에 다시 집어넣는 과정을 분리해 생각해보는 것이 도움이 될 것이다.

지불해야하는 금액은 물품의 이동거리에만 비례하므로 인부의 수 K와는 아무런 상관관계가 없음을 관찰하자.

답(비용)이 32비트 정수로 표현 가능한 범위를 넘어설 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M, K;

ll arr1[10001], arr2[10001];
ll total1 = 0, total2 = 0, total;
ll ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		ll& cur = arr1[i];
		cin >> cur;
		total1 += cur;
	}
	for (int i = 1; i <= M; i++) {
		ll& cur = arr2[i];
		cin >> cur;
		total2 += cur;
	}

	total = min(total1, total2);
	total1 = total2 = total;
	for (ll i = 1; total1 > 0; i++) {
		ll& cur = arr1[i];
		if (cur <= total1) {
			ans += i * cur;
			total1 -= cur;
		}
		else {
			ans += i * total1;
			total1 = 0;
		}
	}
	for (ll i = 1; total2 > 0; i++) {
		ll& cur = arr2[i];
		if (cur <= total2) {
			ans += i * cur;
			total2 -= cur;
		}
		else {
			ans += i * total2;
			total2 = 0;
		}
	}

	cout << total << ' ' << ans;
}