[백준 / C++] 11399번 ATM

문제 재정의 및 추상화

결론: 중첩되는 합의 최솟값을 구하라

문제 접근 방식

• 앞 사람 시간이 짧을수록 전체 합이 작아진다.
  -> 정렬 함수 sort 를 이용하자!

해법을 찾는데 결정적이었던 깨달음

📌 생각하는대로 풀면 된다. 최선의 값을 찾는 말 그대로 그리디!

문제 풀이 로직

1. 사람 수 n을 입력받는다.
2. 사람 수만큼 각 사람별로 걸리는 시간을 vector p에 입력받는다.
3. p를 오름차순 정렬한다.
4. n번 반복하며 0번째부터 i번째까지의 합을 구하고 최종값 sum에 해당 합을 계속 더해준다.
5. sum을 출력한다.

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> p;
    int n, tmp, sum = 0;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> tmp;
        p.push_back(tmp);
    }
    
    sort(p.begin(), p.end());
    
    tmp = 0;
    
    for(int i = 0; i < n; i++){
        tmp += p[i]; // 0번째부터 i번째까지의 합
        sum += tmp; // 전체 합(결과값)
    }
    
    cout << sum;
    
    return 0;
	}
}