[BOJ] 11399 ATM

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

11399번: ATM

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

sort + greedy

 

---------------------------------------------------풀이----------------------------------------------------

 

첫 번째 사람의 시간은 N번 더해지고,

두 번째 사람의 시간은 N-1번 더해지고,

세 번째 사람의 시간은 N-2번 더해지는 것을 반복한다.

즉, 작은 숫자가 앞에 올수록 유리한 것이다.

따라서 오름차순 정렬을 한 뒤, N-i를 곱해 전부 더해준다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int Pi[1001] = {0, };
int N;

// 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값=?
int main(void){
    FASTIO;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> Pi[i];
    }
    sort(Pi, Pi+N);
    int ans = 0;
    for(int i = 0; i < N; i++){
        ans += Pi[i]*(N-i);
    }
    cout << ans << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

예시가 없었으면 파악하는데 조금 걸렸을 것 같다.