BOJ 11399 - ATM

https://www.acmicpc.net/problem/11399

11399번: ATM

 

Greedy 알고리즘을 이용해서 푸는 문제이다.

이 문제를 풀면서 내가 겪었던 가장 큰 문제는

DP 와 Greedy 의 개념을 명확하게 이해하지 못하고 있다는 점이었다.

 

DP 는 가능한 모든 경우의 수를 다 따지되 메모이제이션 기법을 써서 연산의 횟수를 줄이는 것이고,

Greedy 는 그냥 지금 현재 상황에서 가장 최적의 선택지만 고르면 되는것이다.

 

이에 대한 명확한 이해도가 없다보니

이 문제를 풀 때 모든 경우의 수를 어떻게 다 구해서

최소의 답을 찾아낼까 생각을 하고 있느라 풀지 못하고 있었다.

 

 

이 문제는 ATM 기기에 사람들이 줄을 서 있고,

사람마다 걸리는 시간이 P 배열 값으로 주어진다.

 

사람 수가 5명 일 때(N = 5), P = [3, 1, 4, 3, 2] 라고 하면,

그냥 이순서대로 했을 때의 걸리는 총 시간은

3 + (3 + 1) + (3 + 1 + 4) + (3 + 1 + 4 + 3) + (3 + 1 + 4 + 3 + 2) = 39 가 된다.

 

이 경우의 가장 적은 시간이 걸리게 하는 방법은

P = [1, 2, 3, 3, 4] 이면 된다.

 

1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 3) + (1 + 2 + 3 + 3 + 4) = 32 가 되며,

 

그냥 P 배열 자체를 오름 차순으로 정렬하면 된다.

 

간단하게 C++ STL 에서 제공하는 algorithm 헤더에 정의된

sort() 를 사용하면 O(NlogN) 에 끝낼 수 있기 때문에 시간 초과도 뜨지 않게 된다.

(sort() 는 quick sort 기반이다)

 

- c++

#include <algorithm>
#include <iostream>
#define MAX 1001
 
using namespace std;
 
int N;
int P[MAX];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }
 
    sort(P, P + N);
 
    int sum = 0;
    for (int i = 1; i < N; i++) {
        P[i] = P[i - 1] + P[i];
    }
 
    for (int i = 0; i < N; i++) {
        sum += P[i];
    }
 
    cout << sum;
 
    return 0;
}