백준 1715번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 4

---

풀이

 15903번 문제와 거의 같은 문제이다. 당시 문제 풀이는 https://codejin.tistory.com/203 에서 확인할 수 있다.

백준 15903번 C++ 풀이

 

결국은 제일 작은값 끼리 더해나가면서 값이 증가하는 폭을 최대한 줄이면 최종적인 합도 최솟값이 된다. 그리디하게 풀이하는 문제다.

코드

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

priority_queue<int> pq;

void input() {
	int n, data;
	cin >> n;

	while(n--) {
		cin >> data;
		pq.push(-data);
	}
}

void sol() {
	int a, b, ans = 0;
	while(pq.size() > 1) {
		a = pq.top(); pq.pop();
		b = pq.top(); pq.pop();
		ans -= a + b;
		pq.push(a + b);
	}
	cout << ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}