15903번 - 카드 합체 놀이(c++)
🗒 15903번 문제
📌 priority Queue를 사용해서 오름차순의 큐를 받아라 ❗️
1️⃣ 카드 합체 놀이 문제는 서로 다른 카드 두 장을 m번 합체 시켜서 최소 점수를 만들어야 한다.
2️⃣ 가장 작은 값끼리 계속 합체하는 경우가 가장 작은 값을 만든다.
3️⃣ priority queue는 내림차순으로 큐가 정렬되어 있기에 오름차순으로 값을 받아내기 위해서는 -(값)을 넣어준다.
4️⃣ top에 있는 값을 연속 두번 꺼내서 그 두 값을 더하고 그 합을 큐에 다시 넣는다.
5️⃣ 합해서 들어간 값은 그 값의 위치에 맞게 들어가 진다. -> priority queue이기에!
6️⃣ 들어가는 자연수 값이 1,000,000까지 가능하기에 들어가는 값을 long long 타입으로 선언하자.
➰ 코드로 나타낸 15903번 ➰
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
priority_queue<long long> pq;
int n, m;
long long num, answer = 0;
cin >> n >> m ;
// 먼저 숫자들을 받는다.
while (n--) {
cin >> num;
pq.push(-num);
}
// 합체 가능 횟수만큼 while문을 돌리자
while (m--) {
// 첫번째 top, 두번째 top를 저장하고 두 값을 queue에서 뺀다.
// 그 두 값의 합을 큐에 두 번 저장 -> 카드 두개의 값이 변경되었기에
long long first = -pq.top();
pq.pop();
long long second = -pq.top();
pq.pop();
long long sum = first + second;
pq.push(-sum);
pq.push(-sum);
}
while (!pq.empty()) {
answer += (-pq.top());
pq.pop();
}
cout << answer << endl;
return 0;
}
Author And Source
이 문제에 관하여(15903번 - 카드 합체 놀이(c++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoonah-dev/15903번-카드-합체-놀이c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)