[백준] 알고리즘 11399번 - ATM 문제

ATM

www.acmicpc.net/problem/11399

11399번: ATM

소스코드

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n,cnt=0;
   cin >> n;
   vector<pair<int,int>> v;
   for (int i = 0; i < n; i++) {
	   int t;
	   cin >> t;
	   v.push_back({ i,t });
   }
   sort(v.begin(), v.end(),cmp);
   int size = v.size();
   int ans = 0;
   for (int i = 0; i < size; i++) {
	   cnt += v[i].second;
	   ans += cnt;
   }
   cout << ans;
}

해결방법

문제의 예시에서 유추할 수 있듯이, 가장 적합한 방법은 인출시간이 짧은 순서대로 주르륵 계산해주면 정답이된다.

그리디 알고리즘에서는 어떻게 정답을 도출하는가의 키포인트가 중요한데 이런점을 빠르게 찾는 연습을 하는게 빠른 문제풀이에 도움이 된다.