[BOJ]11399 - ATM [C++]

문제 분류에서 그리디 알고리즘으로 분류되어 있는 문제입니다.

N명의 사람들이 각각 돈을 인출하는데 N분이 걸립니다.

이 문제에서는 모든 사람들이 인출하는데까지 최단시간이 걸리게 해야합니다.

그러려면, 인출하는데 시간이 짧게 걸리는 사람부터 돈을 인출하게 되면, 최단시간이 나오게 됩니다.

 

위 문제에서 주어진 예제를 보면 순서를 바꾸지 않고 그냥 진행하게 되면 각 사람들이 돈을 인출하는데 걸리는 시간의 합이 39분이 나옵니다.

여기서 시간이 짧게 걸리는 순으로 나열해서 계산을 하게되면 총 32분으로 시간이 단축됩니다.

 

그러면 프로그램의 흐름은, 시간을 내림차순으로 정리하고,

1번 사람 시간 + (1번 사람 시간 + 2번 사람 시간) + ....+(1번 사람 시간 +...+ n번 사람 시간)

이렇게 계산하면 됩니다.

 

코드 보겠습니다.

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;

int main() {
	int n, tmp = 0, tot = 0;
	int time[1000] = { 0, };

	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> time[i];

	sort(time, time  + n);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			tmp += time[j];
		}
			tot += tmp;
			tmp = 0;
	}

	cout << tot;
}

감사합니다.