백준 1715 [C++]

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

1. 풀이방법

 

 

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

 

 

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

 

 

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

 

 

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

 

 

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

 

 

 

 

2. 주의사항

 

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

 

 

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

 

 

- 어 큐에 들어가므로 sort를 할 필요가 없다.

 

 

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

 

 

 

3. 나의코드

 

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}