백준 1715 카드 정렬하기

HUSII·2023년 2월 7일
0

코딩 문제풀이

목록 보기
1/1

출처
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개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

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

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


우선순위 큐를 이용하여 푸는 문제

우선순위 큐에 있는 카드 묶음 중 가작 작은 두개의 카드 묶음을 더해준다
더한 결과를 result에 더해주고,
다시 우선순위 큐에 등록해준다 -> 다시 더해질수도 있기 때문에

우선순위 큐에 항상 카드묶음이 2개씩 있다고 프로그램이 실행되기 때문에 1개일때의 예외를 설정해줘야한다.

카드묶음이 1개일때는 그냥 0을 출력해야한다.
비교를 아예 안하기 때문이다.

전체 코드

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

class baekjoon {
public:
	long result = 0;
	int n;
	priority_queue<int, vector<int>, greater<int>> card_set;

	void input();
	void solve();
	void print();
};

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	baekjoon bj;
	bj.input();
	bj.solve();
	bj.print();

	return 0;
}

void baekjoon::input() {
	;
	int temp;

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> temp;
		card_set.push(temp);
	}
}

void baekjoon::solve() {
	;
	long first_set = 0, second_set = 0;
	while (1) {
		// pop first card_set
		first_set = card_set.top();
		card_set.pop();

		// pop second card_set
		if (card_set.empty()) {
			result += result + first_set;
			break;
		}
		second_set = card_set.top();
		card_set.pop();

		// plus
		result += first_set + second_set;

		if (card_set.empty()) break;
		card_set.push(first_set + second_set);
	}
}

void baekjoon::print() {
	;
	if (n == 1) cout << "0\n";
	else cout << result << '\n';
}

항상 작은 카드 묶음을 더해준다는 생각을 못해서 애먹었던 문제
문제를 더 자주 풀어야 감이 좋아질듯 하다.

profile
공부하다가 생긴 궁금한 것들을 정리하는 공간

0개의 댓글