11399. ATM

그리디 문제이다.

---

1. 문제 풀이

2. Solution

3. 알아야 할 개념

---

1. 문제 풀이

필자는 ATM 문제를 그리디 문제로 해결했다. 

ATM 문제에서 탐욕법은 "시간이 적게 걸리는 사람부터 ATM 사용하기" 이다. 

ATM 문제에서는 1번으로 ATM을 사용하는 사람이 N번 사용시간이 더해지고, 2번 사람은 N-1번 사용시간이 더해지고,,,, N번 사람은 1번 더해지기 때문이다. 

 

2. Solution

// 백준 11399 ATM
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minTime(int N, vector<int>& person)
{
    // 시간이 적게 걸리는 사람이 앞으로 오도록 정렬
    sort(person.begin(), person.end());


    // 총 소요시간 계산
    int total = 0;
    for(int i = 0; i < N; i++)
    {
        total += person[i] * (N - i);
    }

    return total;
}

int main()
{
    int N;
    vector<int> person;

    cin >> N;
    for(int i = 0; i < N; i++) 
    {
        int n;
        cin >> n;
        person.push_back(n);
    }
    cout << minTime(N, person) << endl;

    return 0;
}

3. 알아야 할 개념

vector에 값을 할당할 때, vector 크기를 초기화하지 않았다면 RunTime Error 가 발생한다.

RunTime Error 발생

올바른 vector 값 할당