[C++] 15903번. 카드 합체 놀이

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

15903번: 카드 합체 놀이

1. 문제

2. 아이디어

기본적으로 그리디 알고리즘이다.

가장 작은 카드를 더해서 카드 뭉치를 업데이트해주면 된다.

 

그러면 가장 작은 요소로 배열을 정렬해서 하는 방법이 있는데,

이는 조금 문제가 있다.

 

왜냐면, 업데이트 + 정렬 + 업데이트 + 정렬은 생각보다 비용이 크기 때문이다.

정렬의 경우 아무리 빨라봐야 평균 n log n 시간 복잡도가 소모된다.

 

시간 제한이 1초가 걸려있기 때문에 정렬은 조금 부담스러울 수 있다.

 

그러므로 항상 최소값을 보장하는 최소 힙을 이용한 우선순위 큐를 활용하면

log n 만에 최소값을 찾아낼 수 있다.

 

우선순위큐가 주된 아이디어다.

 

3. 풀이

 

 

문제 풀이에 필요한 변수들 선언

최소 힙으로 우선순위큐를 정의해야하며,

long long을 써준 이유는

 

카드의 처음 상태는 1~1'000'000 의 값을 가지는데

M번의 카드를 합치기를 반복할 경우 (M은 15xN 에다가 N의 최대값은 1000 이므로 최대 15000)

최대 150억의 수가 나올 수 있기 때문에, int 형으로는 값을 커버하지 못한다.

그러므로 long long 이나 __int64 를 써줘야만 한다.

 

 

이것이 메인 로직

 

 

출력 아래는 전체코드다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

priority_queue<long long, vector<long long>, greater<long long>> pq;
int M, N;

int main()
{
	/* 입력 */
	{
		cin >> N >> M;
		//N: 카드의 수
		//M: 카드 게임을 하는 횟수

		for (int i = 0; i < N; i++)
		{
			long long input;
			cin >> input;
			pq.push(input);
		}

	}


	/* 로직 */
	{
		for(int i=0;i<M;i++)
		{

			long long first = pq.top();
			pq.pop();

			long long second = pq.top();
			pq.pop();

			long long inputNumber = first + second;
			pq.push(inputNumber);
			pq.push(inputNumber);
		}
	}


	/* 출력 */
	{
		long long sum = 0;

		while (!pq.empty())
		{
			sum += pq.top();
			pq.pop();
		}
		
		cout << sum << endl;
	}

}

 

 

상당히 쉽게 풀었는데,

계속 틀렸다고 나와서 그 이유를 찾아보니까

자료형 문제였다..

 

자료형은 잘 확인하도록 하자..