[백준] 1715번 - 카드 정렬하기

www.acmicpc.net

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

문제

💡

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

시간 제한: 2초

메모리 제한: 128MB

입력

💡

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

💡

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력	예제 출력
3 10 20 40	100
4 30 40 50 100	410

풀이

덱을 효율적으로 비교하기 위해 배열은 오름차순으로 정렬되어야 한다.

여기서 덱의 자료구조로 적절한 것은 priority_queue와 deque+sort 두 가지가 있는데, 추출된 덱은 계속 대소 비교가 필요하므로 원소가 추가될 때 마다 정렬시키는 priority_queue가 적절하다. 여기에 오름차순으로 바꾸기 위해 greater<int>를 사용하였다.

두 원소를 비교하기 위해 배열에 최소 원소 두 개가 있어야 하므로 while을 통해 반복하면서 배열 크기를 확인하였다.

코드


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

int main() {
	int N, C;
	priority_queue<int, vector<int>, std::greater<int>> pq;
	cin >> N;

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

	int answer = 0;

	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		answer += a + b;
		pq.push(a + b);
	}

	cout << answer;
	
	return 0;
}

후기

처음에 문제의 의도를 오해해 누적합을 말하는 줄 알았는데 그것이 아니었다. 문제 지문 중 (10 + 20) + (30 + 40) 예시를 잘 보면 30은 이전의 두 값을 더한 값이지만, 40보다 앞에 있으므로 합쳐진 덱도 다른 덱과 합쳐야할 요소임을 보여준다. 따라서 배열의 맨 앞 두 요소를 더하고 다시 배열에 추가를 반복하는 식으로 풀어야 한다.

정렬을 하기 위해 greater를 사용했는데, 이 키워드에 대해 궁금증이 생겼다. vector였다면, sort를 할 때 정렬하기 위해 comp함수를 만들어 매개변수로 사용하는데, 정렬의 규칙을 생성시 정하는 priority_queue에서도 comp가 함수이지 않을까 생각했는데 사실 struct라고 한다.

정확히는 함수 객체라고 하는데, 함수 객체는 함수처럼 사용할 수 있는 객체라고 한다. 쉽게 설명하면 strut인데, ()연산자를 오버로딩해서 함수인 척? 하는것이다.


struct comp{
    int operator()(int a, int b) const{
        return a < b;
    }
}

decltype키워드 쓰거나 람다로 하는 방법보다 함수객체 방식이 그냥 깔끔하고 std에서도 저런 식으로 사용한다고 하니, 다음에 잘 활용해야겠다.