BOJ 11399 - ATM [C++] / Greedy Algorithm

11399번: ATM (acmicpc.net)

11399번: ATM

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 출력

 

간단히 생각해보면 쉬운 문제이다.

글의 제목에서부터 알 수 있듯이, Greedy Algorithm을 사용하면 되는데, 그냥 논리적으로 생각해보면 너무나도 자명한 사실로 문제를 풀 수 있다.

 

우선 문제 설명에 나와있는 케이스로 생각해보자.

5명의 순서가 [3 1 4 3 2] 로 서있는 경우를 생각해보면, 

 

1번은 3분

2번은 3+1 분

3번은 3+1+4 분

4번은 3+1+4+3 분

5번은 3+1+4+3+2 분

이 걸리는 것을 알 수 있다.

 

즉, 이 모든 것을 더한 값이 "최소값"이 되려면?

 

당연히 가장 시간이 적게 걸리는 사람이 맨 앞 부터 배치되면서 최대한 많이 더해지게 하고, 가장 시간이 많이 걸리는 사람이 최대한 뒤 쪽으로 밀리면서 최대한 적게 더해지게 하는 것이다!

 

-> 일종의 Greedy Algorithm인 것이다.

 

따라서 이 문제는, 주어진 n개의 수를 그냥 오름차순 정렬한 뒤에, 그 값들을 하나하나씩 더 해주면 끝나는 문제로 바뀐 것이다.

 

내가 제출한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test_case;
    cin >> test_case;
    cin.ignore();
    int ans;
    string s;
    getline(cin, s);
    istringstream ss(s);
    vector <int> anslist;
    while (ss >> ans) anslist.push_back(ans);
    int sum = 0;
    sort(anslist.begin(),anslist.end());
    for (int i=0;i<test_case;i++){
        sum += anslist[i]*(test_case-i);
    }
    cout << sum;

    return 0;
}

벡터 자료구조를 사용해서, 입력받은 값들을 우선 밀어넣은 후에, sort 함수를 사용하여 오름차순 정렬했다.

 

이후에, 앞에서부터 (n-i)을 곱해주면서 나가는게 핵심이다.

 

맨 첫 번째 원소는 n번 더해질 것이고, 그 다음은 n-1번, 그 다음은 n-2번... 더해질 것이기에 곱하기로 깔끔하게 처리할 수 있다.