[그리디] 카드 합체 놀이(15903)(C++)

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

15903번: 카드 합체 놀이

 

1. 문제 개요

 

석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

카드 정렬하기 문제와 굉장히 유사한 문제이다.

우선순위큐를 사용해서 최소값을 뽑아내도록 하고, 가장 최소값을 갖는 카드 두 장을 정해진 수만큼 더하면 된다.

처음에 int 형을 사용해서 문제를 해결하려다 틀려서 long long 을 사용해서 맞았다.

수의 범위를 잘 살펴보고 자료형 선택하기 꼭 기억하자 ...

 

 

4. 전체 코드

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    int n,m;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    scanf("%d%d",&n,&m);
    
    int temp;
    for(int i=0;i<n;i++) {
        scanf("%d",&temp);
        pq.push(temp);
    }
    
    for(int i=0;i<m;i++) {
        long long temp = pq.top();
        pq.pop();
        temp += pq.top();
        pq.pop();
        pq.push(temp);
        pq.push(temp);
    }
    
    long long sum = 0;
    while(pq.size()>0) {
        sum += pq.top();
        pq.pop();
    }
    
    printf("%lld",sum);
}