BOJ 11399 - ATM

문제 링크

문제#

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 $N$명의 사람들이 줄을 서있다. 사람은 1번부터 $N$번까지 번호가 매겨져 있으며, $i$번 사람이 돈을 인출하는데 걸리는 시간은 $P_i$분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, $P_1 = 3$, $P_2 = 1$, $P_3 = 4$, $P_4 = 3$, $P_5 = 2$인 경우를 생각해보자. $[1, 2, 3, 4, 5]$ 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, $3+1 = 4$분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 $3+1+4 = 8$분이 필요하게 된다. 4번 사람은 $3+1+4+3 = 11$분, 5번 사람은 $3+1+4+3+2 = 13$분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 $3+4+8+11+13 = 39$분이 된다.

줄을 $[2, 5, 1, 4, 3]$ 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 $1+2 = 3$분, 1번 사람은 $1+2+3 = 6$분, 4번 사람은 $1+2+3+3 = 9$분, 3번 사람은 $1+2+3+3+4 = 13$분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 $1+3+6+9+13 = 32$분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 $N$과 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 사람의 수 $N(1 \le N \le 1{,}000)$이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$가 주어진다. $(1 \le P_i \le 1{,}000)$

출력#

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

풀이#

전체 대기시간은 앞에 선 사람의 인출 시간이 뒤 사람들에게 계속 누적되는 구조다. 따라서 짧은 시간이 앞에 올수록 여러 사람의 기다림을 동시에 줄일 수 있으므로, 인출 시간을 오름차순으로 정렬하는 그리디가 최적이다.

코드에서는 정렬한 배열을 앞에서부터 누적합으로 바꾸며 각 사람이 기다린 총 시간을 더한다. 예를 들어 P[j] += P[j - 1]는 j번째 사람까지 걸린 시간을 의미하고, 이 값들을 모두 합한 것이 문제에서 요구하는 최소 총합이다.

핵심은 한 사람의 시간이 뒤에 있는 모든 사람에게 영향을 준다는 점이다. 그래서 긴 시간을 뒤로 보내는 선택이 전체 합을 가장 작게 만든다.

코드#

#include <iostream>
#include <algorithm>
using namespace std;
 
int P[1001];
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N;
	cin >> N;
 
	for (int i = 0; i < N; i++) 
		cin >> P[i];
 
	sort(P, P + N);
 
	int answer = P[0];
	for (int j = 1; j < N; j++) {
		P[j] += P[j - 1];
		answer += P[j];
	}
 
	cout << answer << '\n';
	return 0;
}

복잡도#

• 시간 복잡도: 인출 시간을 정렬하므로 $O(N \log N)$이다.
• 공간 복잡도: 인출 시간 배열을 저장하므로 $O(N)$이다.

마무리#

짧은 인출 시간을 앞에 세우는 순간 전체 대기시간이 가장 많이 줄어든다.