[백준 11399] ATM cpp

문제
한 대의 ATM기기 앞에 N명의 사람들이 줄 서 있으며 각 사람들이 돈을 뽑는 시간은 다르다. 
만약 첫 번째 사람이 2분 두 번째 사람이 3분이라면 두 번째 사람은 총 5분이 소요되고 첫 번째 사람은 2분이 소요되어 두 사람이 모두 돈을 뽑으려면 7분이 걸리게 된다.
이처럼 N명의 사람이 돈을 뽑을 때 최소한의 시간으로 뽑을 수 있는 시간은 몇인지 구하라

입력
첫째 줄에 사람의 수 N(1이상 1000이하)
둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간을 입력한다.(1이상 1000이하)

출력
사람들이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력

---

만약 5분이 걸리는 사람과 1분이 걸리는 사람이 있을 때 5분이 걸리는 사람이 먼저 뽑게되면 두 번째 사람은 6분이 소요된다. 따라서 시간이 적게 걸리는 사람먼저 돈을 인출할 수 있도록 해야한다.

 

이 문제는 아주 간단히 그리디 알고리즘을 이해하기 위해 풀어본다.

그리디 알고리즘의 개념으로 매 선택마다 최적의 선택을 하여 최적해를 구하는 것이다. 

여기서 매 선택은 한 대의 ATM기기에 어떤 사람이 뽑을지 정하는 것이다. 이를 시간이 적게 걸리는 사람을 먼저 선택하여 인출하도록 하였고 최종적으로 최솟값을 구할 수 있었다.

 

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

int N;
int time[1000];
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> time[i];
	}
	sort(time, time + N);
	
	int answer = 0;
    
    // 현재 돈을 인출하려는 사람의 소요시간은
    // 이전 사람들의 소요시간과 더해주어야 한다.
    // 따라서 처음부터 해당인덱스까지 모두 더하여 최종해에 다시 더해주었다.
	for (int i = 0; i < N; i++) {
    	// 두 번째 for문이 돌 때마다 sum을 0으로 초기화
		int sum = 0;
		for (int j = 0; j <= i; j++) {
			sum += time[j];
		}
		answer += sum;
	}

	cout << answer << endl;
	return 0;
}