https://www.acmicpc.net/problem/15903
[필자 사고]
그리디 알고리즘이다.
그리디 알고리즘이라고 다를건 없고 최선의 경우의 수로 푸는 문제이다.
필자는 우선순의 큐를 이용하여 앞 2개의 숫자를 꺼내서 해당 문제에서 요구하는 방식대로
코드를 해결해 나갔다.
아래는 자세한 코드해설이다.
[코드 해설]
코드 설명:
- 입력 받기:
- cin >> N >> M으로 N과 M의 값을 입력받습니다.
- N은 주어지는 숫자의 개수이고, M은 두 수를 더하는 연산을 몇 번 반복할지를 나타냅니다.
- 우선순위 큐 초기화:
- priority_queue<long, vector<long>, cmp> pq는 우선순위 큐로, 기본적으로 priority_queue는 큰 값이 먼저 나오게 되어 있는데, 여기서는 cmp라는 비교자 함수를 사용하여 작은 값이 먼저 나오도록 만듭니다. 즉, 오름차순으로 정렬됩니다.
- 우선순위 큐에 수 삽입:
- for문을 통해 N개의 숫자를 입력받고, 우선순위 큐에 넣습니다. 이렇게 하면, 큐는 오름차순으로 정렬된 상태를 유지합니다.
- 두 수 더하기 연산 M번 수행:
- while (M--) 루프를 통해 M번 반복하며, 두 개의 가장 작은 수를 우선순위 큐에서 꺼냅니다.
- 이 두 수를 더한 값을 다시 큐에 두 번 넣습니다. 이렇게 하는 이유는 두 개의 숫자를 더하는 연산을 한 번에 두 번 추가하여, 계속해서 더한 값을 큐에 넣어두기 때문입니다.
- 결과 계산:
- M번의 연산이 끝나고 나면, 우선순위 큐에 남아 있는 모든 수의 합을 구합니다. while (!pq.empty())로 큐가 빌 때까지 반복하면서 큐에서 하나씩 꺼내어 resultNum에 더해줍니다.
- 결과 출력:
- 마지막으로, cout << resultNum을 통해 우선순위 큐에 남은 모든 수들의 합을 출력합니다.
코드 흐름:
- 처음에는 N개의 수를 우선순위 큐에 넣고, 그 후 M번 동안 두 개의 가장 작은 수를 더해서 그 값을 큐에 다시 넣습니다.
- M번의 연산 후에는 우선순위 큐에 남은 값들을 모두 더한 후 그 합을 출력합니다.
[소스 코드]
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
typedef struct cmp {
bool operator() (long a, long b) {
return a > b;
}
}cmp;
priority_queue<long, vector<long>, cmp> pq;
int main(void) {
cin >> N >> M;
for (int i = 0; i < N; i++) {
long num;
cin >> num;
pq.push(num);
}
while (M--) {
long firstNum = pq.top();
pq.pop();
long secondNum = pq.top();
pq.pop();
long sumNum = firstNum + secondNum;
pq.push(sumNum);
pq.push(sumNum);
}
long resultNum = 0;
while (!pq.empty()) {
resultNum += pq.top();
pq.pop();
}
cout << resultNum;
}