[BOJ] 백준 11399번 ATM C++

16 Jun 2019

Reading time ~1 minute

이번문제는 백준(boj) 11399번 ATM 이라는 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/11399

풀이

이 문제는 탐욕법으로 푸는 문제 입니다.

사실 탐욕법이라고 뭐 거창 한 것은 아닙니다.

매번 최적이다 싶은 방법으로 진행을 하시면 됩니다.

완전히 동일한 결과를 얻지 못하더라도 가장 근사 하게나마 구하는 것을

탐욕법이라고 합니다.

이문제의 핵심은 빨리 걸리는 사람을 빨리 시켜주고 보내버리는게

전체의 합을 가장 줄이는 길입니다.

저는 따로 배열이나 벡터를 만들지는 않았습니다.

어차피 만들어서 소팅 할 꺼

처음부터 priority_queue (우선순위 큐) 를 이용하여

받아서 문제를 풀었습니다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;


int main() {
	int n;
	int temp;
	int result = 0;
	int sum = 0;
	priority_queue<int,vector<int>,greater<int>> pq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		pq.push(temp);
	}
	while (!pq.empty()) {
		result = result + pq.top();
		sum = sum + result;
		pq.pop();
	}
	cout << sum;
	return 0;
}