https://www.acmicpc.net/problem/1715
이 문제는 어떻게 카드를 합쳐 나갈 때 비교 횟수가 적어지는지 파악하는 그리디 알고리즘 문제라고 볼 수 있다. 정말 쉽게 생각하면 방법은 매우 간단합니다. 가장 작은 수의 카드 묶음을 더 해나간다면 자연스럽게 제일 비교 횟수가 적은 방법을 찾게 됩니다.
EX1)
30 50 100 300 320
30+50 sum = 80
80 100 300 320
80+100 sum= 80+180
180 300 320
180+300 sum= 80+180 + 480
320 480
320+480 sum= 80+ 180 + 480 + 800 (가장 비교 횟수가 적은경우)
800
EX2)
10 20 40
10+20 sum = 30;
30 40
70 sum = 30+70; (가장 비교 횟수가 적은경우)
위 예시를 참고해서 코드를 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> pq;
int main() {
int n;
cin >> n;
int num;
long long sum = 0;
while (n--)
{
cin >> num;
pq.push(num);
}
if (n == 1)
{
cout << pq.top() << '\n';
}
else
{
while (pq.size() != 1)
{
int n1, n2;
n1 = pq.top();
pq.pop();
n2 = pq.top();
pq.pop();
pq.push(n1 + n2);
sum = sum + n1 + n2;
}
}
cout << sum << '\n';
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 2075번: N번째 큰 수 (C++) (0) | 2024.02.02 |
---|---|
백준 1927번: 최소 힙 (C++) (0) | 2024.02.02 |
백준 2948번: 2009년 (C++) (1) | 2024.01.31 |
백준 1924번: 2007년 (C++) (0) | 2024.01.31 |
백준 11286번: 절댓값 힙 (C++) (0) | 2024.01.31 |