[백준, BOJ] 11399 - ATM (C++)

안녕하세요! 오늘은 BOJ 11399 - ATM 문제를 풀어볼게요.

 

문제를 읽어보면, 이 문제는 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 문제예요.

 

접근

 

문제에 있는 예시를 보고 접근해 볼게요.

 

첫 번째 예시에서는 [1, 2, 3, 4, 5] 순서로 줄을 섰어요.

맨 처음 사람이 1번 사람이니, 3분이 필요해서 뒷사람 모두가 3분이 누적돼요.

 

두 번째 예시에서는 [2, 5, 1, 4, 3] 순서로 줄을 섰어요.

맨 처음 사람이 2번 사람이니, 1분이 필요해서 뒷사람 모두가 1분을 누적돼요.

여기에서 최종적으로 걸리는 시간의 합이 사람들이 줄을 서는 순서에 따라 달라짐을 알 수 있어요.

 

첫 번째 사람에 대해서만 언급했지만, 두 번째 사람도 시간이 짧게 걸리는 사람이 와야 두 번째 사람부터 마지막 사람까지 누적되는 시간이 적겠죠?

그러면 일반화해 봤을 때, 최솟값을 구하려면 돈을 인출하는 데 필요한 시간이 짧은 사람이 앞으로 와야 해요.

오름차순으로 정렬해서 합을 구하면 문제가 해결될 것 같네요! (그리디 + 정렬)

 

구현

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

int wait[1001];

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

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

    sort(wait, wait+n);
    // 그리디: 결국 돈을 인출하는 데 걸리는 시간이 짧은 사람부터 줄을 서는 것이 시간의 합이 최소가 됨!

    int sum = 0;
    for (int i = 0; i < n; i++) { // i번째 사람이 돈을 인출하는 데 걸리는 시간:
        for (int j = 0; j <= i; j++) { // 0 ~ i번째 사람이 돈을 인출하는 데 걸리는 시간의 합!
            sum += wait[j];
        }
    }
    cout << sum;
    return 0;
}

 

구현에서 특별하게 어려운 점은 없는데, i번째 사람이 돈을 인출하는 데 걸리는 시간이 0번째 사람부터 i번째 사람이 돈을 인출하는 데에 걸리는 시간의 합이라는 것을 이중 for문을 통해 구현하는 것이 핵심이 되겠네요.