백준 알고리즘 11399번: ATM [C++]

문제 출처: www.acmicpc.net/problem/11399

11399번: ATM

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n;
	int arr[1001];
	int result[1001];
	int sum;

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

	sort(arr, arr + n);
	sum = result[0] = arr[0];
	for (int i = 1; i < n; i++)
	{
		result[i] = result[i - 1] + arr[i];
		sum += result[i];
	}
	cout << sum;
	return 0;
}

(실행)

2. 풀이

문제를 자세히 읽어보면 예시로 나온 가장 빠른 경우는 돈을 인출할 때 걸리는 시간을 오름차순으로 나열되어 있다. 그렇다면 오름차순으로 정렬을 해주고, 배열을 이용하여 각 순서에서 걸리는 시간을 측정한 후 합계를 sum에 저장하여 출력하면 된다.

3. 느낀 점

그리디 알고리즘이라고 해서 조금 긴장했는데 생각보다 쉬운 문제였다. 하지만 어느부분이 그리디 알고리즘인지 잘 이해하지 못해서 다른 문제를 풀기 전에 그리디 알고리즘을 풀어보야겠다.