백준 13975 c++ "파일 합치기 3" -PlusUltraCode-

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

 

[필자 사고]

greedy 알고리즘 이용하여 풀면 쉽게 풀 수 있다.

필자는 해당 문제를 우선순위 큐를 이용하여 첫번째 수와 두번째 수를 꺼내서 합한뒤 resultSum에 더해주는 형태로

해당 문제를 해결했따.

 

아래는 자세한 코드 해설이다.

[코드 해설]

 문제 배경 (직관적인 예시)

• N개의 숫자 묶음이 있고, 한 번 두 개를 합칠 때마다 그 합만큼의 비용이 든다고 가정합니다.
• 이 과정을 반복해서 하나로 합쳐야 할 때, 전체 합산 비용의 최소값을 구하는 것이 목표입니다.
• 가장 작은 숫자 두 개씩 합쳐나가는 것이 항상 최적의 선택입니다. → 그래서 min-heap (우선순위 큐) 사용

---

🔧 함수 설명

1. main()

• 테스트 케이스 개수 T를 입력받고, 각 테스트 케이스마다 Input() → Game_Start() 실행

---

2. Input()

• 우선순위 큐 pq를 초기화 (비우기)
• 숫자 개수 N 입력
• N개의 숫자를 입력받아 **작은 수가 우선 나오는 최소 힙(greater<long>)**에 저장

---

3. pqPop()

• 현재 큐에서 가장 작은 두 수를 꺼내 합친 값을 반환
• 이 합은 누적 비용이 되며, 다시 큐에 삽입되어야 함

---

4. Game_Start()

• 총 누적 비용 resultSum을 0으로 시작
• 큐의 크기가 1이 될 때까지:
  • pqPop()으로 두 수를 꺼내 합친 뒤 누적
  • 합친 결과를 다시 큐에 삽입 (다음 연산의 입력이 됨)
• 모든 연산 후 누적 비용을 출력

---

 핵심 알고리즘 요약

1. 항상 가장 작은 두 수부터 합친다 → 그리디 알고리즘
2. 합친 값은 다음에도 사용되므로 다시 큐에 넣는다
3. 이 과정을 반복하여 최소의 총합 비용을 계산

[소스 코드]

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

void Print() {
	cout << pq.top() << '\n';
}

void Input() {
	
	while (!pq.empty()) {
		pq.pop();
	}

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

long pqPop() {
	long resultSum = 0;

	long firstNum = pq.top();
	pq.pop();
	long secondNum = pq.top();
	pq.pop();

	resultSum = firstNum + secondNum;
	return resultSum;
}

void Game_Start() {

	long resultSum = 0;

	while (!pq.empty()) {
		if ((int)pq.size() == 1)break;
		long sum = pqPop();
		resultSum += sum;
		pq.push(sum);
	}

	cout << resultSum << '\n';
}

int main(void) {
	cin >> T;
	while (T--) {
		Input();
		Game_Start();
	}
}