[Advanced][정올] 1190번 : 모두더하기

1190 : 모두더하기 

JUNGOL

 

[풀이 후기]
난이도 : ★★☆☆ (Advanced)
문제 종류 : Sort
해결 방법 : Heap Sort

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

---

 

문제

 

 

문제 분석

1. 두 수를 더할 때, 두 수의 합만큼의 "비용"이 발생한다. 
2. N개의 수를 그냥 더하는 것이 아니라, 최소의 "비용"으로 더해야한다. 
3. 10만 이하의 자연수 5000개를 서로 더할 수 있으므로, int 범위를 넘을 수 있음에 주의하자. 

 

---

 

접근 방법

이 문제의 핵심은 "어떻게 최소의 비용으로 더할 것인가?" 이다. 

 

 

결론부터 말하면, N개의 수를 더할 때, 가장 작은 두 수를 더하는 것이다. 

문제 예시처럼, 1, 2, 3 이 주어진 경우를 살펴보자. 

[ 1, 2, 3 을 더하는 경우 ]

① (1 + 2) + 3   ▶ 비용 = 3
     = 3 + 3        ▶ 비용 = 6
     = 6              ▶ 총 비용 = 9

② (1 + 3) + 2   ▶ 비용 = 4
     = 4 + 2        ▶ 비용 = 6
     = 6              ▶ 총 비용 = 10

③ (2 + 3) + 1   ▶ 비용 = 5
     = 5 + 1        ▶ 비용 = 6
     = 6              ▶ 총 비용 = 11

3개의 수가 있을 때, 가장 작은 두 수를 더하는 ① Case가 총 비용이 가장 작다. 

 

 

 

N개의 수가 있을 때도 마찬가지로 적용된다. 

4개의 수가 있다고 예시를 들어보자. 

[ 1, 2, 3, 4 를 더하는 경우 ]

① (1 + 2) + 3 + 4   ▶ 비용 = 3
    = [ 3, 3, 4 를 더하는 경우 ] 이므로, 다음 방법이 최소 비용이다. 
    = (3 + 3) + 4   ▶ 비용 = 6
    = 6 + 4           ▶ 비용 = 10
    = 10               ▶ 총 비용 = 19

② (1 + 3) + 2 + 4   ▶ 비용 = 4
    = [ 4, 2, 4 를 더하는 경우 ] 이므로, 다음 방법이 최소 비용이다. 
    = (4 + 2) + 4   ▶ 비용 = 6
    = 6 + 4           ▶ 비용 = 10
    = 10               ▶ 총 비용 = 20

③ (1 + 4) + 2 + 3   ▶ 비용 = 5
    = [ 5, 2, 3 를 더하는 경우 ] 이므로, 다음 방법이 최소 비용이다. 
    = (2 + 3) + 5   ▶ 비용 = 5
    = 5 + 5           ▶ 비용 = 10
    = 10               ▶ 총 비용 = 20

④ (2 + 3) + 1 + 4   ▶ 비용 = 5
    = [ 5, 1, 4 를 더하는 경우 ] 이므로, 다음 방법이 최소 비용이다. 
    = (5 + 1) + 4   ▶ 비용 = 6
    = 6 + 4           ▶ 비용 = 10
    = 10               ▶ 총 비용 = 21

.... (생략) ...

 

 

 

덧셈 중간 결과에서 작은 두 수를 찾아야하기 때문에, 아래 과정처럼 Min Heap을 이용해서 해결할 수 있다. 

1. N개의 수를 Min Heap에 push 한다. 
2. pop을 2번해서, 작은 수 2개를 구한다. 
3. 두 수를 더한 비용을 기록하고, 덧셈 결과는 다시 Heap에 push 한다. 
4. Heap Size가 1이 될 때까지 반복한다. 

 

 

* Heap Sort에 관한 내용은 아래 포스팅을 참고하자. 

[자료구조][정렬][C/C++] Heap Sort (우선순위 큐)

[자료구조][정렬][C/C++] Heap Sort (우선순위 큐)

 

 

---

 

코드

먼저, 최소 비용을 계산하는 부분을 살펴보자. 

 

위 접근 방법에서 설명된 1~4 과정을 포함하고 있다. 

int N;
for (int i = 0; i < N; i++) {
	int d;
	scanf("%d", &d);
	push(d);	// N개의 수 push
}

long long ans = 0;
while (heapSize > 1) {
	int a = pop();	// 가장 작은 수1
	int b = pop();	// 가장 작은 수2
	ans += (a + b);	// 두 수를 더한 비용 기록

	push(a + b);	// 두 수의 덧셈 결과 push
}

 

 

Heap과 Main을 포함한 전체 코드를 살펴보자. 

#include <stdio.h>

void swap(int& a, int& b) { int t = a; a = b; b = t; }

const int LM = 5000;
int heap[LM + 5];	// min Heap
int N, heapSize;

void push(int newData) {
	int c = ++heapSize;	// 신규 Data 넣을 위치 (마지막 노드)

	for (; c > 1 && newData < heap[c >> 1]; c >>= 1) {
		heap[c] = heap[c >> 1];
	}
	heap[c] = newData;
}

int pop() {
	int ret = heap[1];
	swap(heap[1], heap[heapSize--]);

	for (int c = 2; c <= heapSize; c <<= 1) {
		if (c < heapSize && heap[c + 1] < heap[c])
			c++;

		if (heap[c] < heap[c >> 1])
			swap(heap[c], heap[c >> 1]);
		else break;
	}
	return ret;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int d;
		scanf("%d", &d);
		push(d);	// N개의 수 push
	}

	long long ans = 0;
	while (heapSize > 1) {
		int a = pop();	// 가장 작은 수1
		int b = pop();	// 가장 작은 수2
		ans += (a + b);	// 두 수를 더한 비용 기록

		push(a + b);	// 두 수의 덧셈 결과 push
	}
	printf("%lld", ans);

	return 0;
}

 

---

 

제출 결과

정올 제출 결과