11399 - ATM - 그리디 알고리즘

문제

문제링크 : https://www.acmicpc.net/problem/11399

풀이전략

1. 각 사람이 돈을 인출하는데 필요한 시간의 최솟값 구하기
2. 단 뒤에서 돈을 뽑는 사람들은 앞에서 뽑는 사람들이 돈을 뽑을 때까지 기다려야한다. 따라서 최솟값을 구하기 위해선 돈을 인출하는데 걸리는 시간이 적은 사람부터 순차적으로 뽑을 때 가장 효율적이다.
3. 인출하는 시간이 짧은 사람부터 뽑는다는 그리디 알고리즘이다ㅏ.

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N;
vector<int> p;


int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d",&N);
    int tmp;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        p.push_back(tmp);
    }

    sort(p.begin(), p.end());
    // 부분합을 만들어 이전 사람들까지 인출할때 걸렸던 모든 시간을 저장한다.
    int pSum = 0;
    int res = 0;

    for(int i=0; i<N; i++){
        pSum += p[i];
        res += pSum;
    }

    printf("%d\n",res);

    return 0;
}

소감

사실 아직 그리디 알고리즘은 당장 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘이다. 아직 깊이 와닿지는 않지만 그럼에도 잘 공부해봐야겠다.