[AlgorithmSolving][탐욕알고리즘] JUNGOL_1929: 책꽂이 만들기

1. 문제 내용

• 문제

  지헌이는 책꽂이를 만들려고 한다. 

  책꽂이의 설계도를 작성하고 보니 길이가 L1, L2, …, LN(1≤Li≤50,000)인 N(1≤N≤20,000)개의 널빤지가 필요하다는 사실을 알았다. 

  지헌이는 목재상에서 필요한 크기(L1+L2+…+LN)의 널빤지를 구입했으나 필요한 크기로 자르기 위해서는 톱이 필요했다.

  지헌이는 아무리 찾아 보아도 톱이 없다는 것을 알고 절망에 빠졌다. 

  이런 모습을 지켜보던 종현이는 지헌이에게 자신이 톱을 빌려줄테니 그 대가로 널빤지를 자를 때마다 그 널빤지의 길이만큼의 비용을 지불하라고 했다. 

  예들 들어 길이가 10인 널빤지를 둘로 나누게 되면 10의 비용을 지불하라는 것이다.

  지헌이는 자신의 어려움에 처해 있다는 것을 이용해서 돈을 벌려고 하는 종헌이가 얄밉기는 했지만 달리 방법이 없어 그렇게 하기로 했다.

  지헌이는 비용을 최소화하기 위해 자르는 위치와 순서를 잘 결정해야만 한다. 

  지헌이가 널빤지를 자르기 위해 필요한 최소한의 비용을 구하는 프로그램을 작성해 보자.

• 입력

  첫 번째 줄에 지헌이가 잘라야 하는 널빤지의 개수 N이 입력되고 이후 N개의 줄에 걸쳐 각 널빤지의 길이를 나타내는 정수가 입력된다.

• 출력

  지헌이가 종현이에게 지불해야하는 비용의 최소값을 출력한다.

• 예제1

  입력:

  3
  8
  5
  8
  

  출력:

  34
  

• 예제2

  입력:

  5
  1
  2
  3
  4
  5
  

  출력:

  33
  

2. 막혔던 지점 (Blockpoint)

해당 문제를 풀기위한 방법이 있는 것을 모른채 문제의 설명만 듣고 두 번째 예제를 진행했을 때 결과값이 “33”이 아닌 “34”가 나와서 막히게 되었습니다. 결과 값이 “34”가 나오는 이유는 다음과 같습니다.

널빤지들의 합은 15이며 가장 큰 널빤지인 5부터 진행

1. 15는 5와 10으로 분리가 되고 비용이 15발생

2. 10은 4와 6으로 분리가 되고 비용이 10발생

3. 6은 3, 3으로 분리가 되고 비용이 6발생

4. 3은 1과 2로 분리가 되고 비용이 3발생

발생한 비용들 15, 10, 6, 3을 모두 더하면 34가 되지만 정답인 “33”이랑 다름

3. 문제에서의 함정 (Trap)

문제를 보면 주어진 널빤지들의 길이를 모두 합한 값에서 정렬된 널빤지들을 값이 큰 수부터 자를 때 사용하도록 예제1을 통해 보여주고 있으며, 단순히 문제의 설명만 가지고는 이 문제를 풀 수 없습니다. 또한 문제의 설명에서는 널빤지를 큰 덩어리에서 원하는 크기로 자르는 것만 강조하여 원하는 크기들을 가장 작은 것부터 합쳐서 하나의 큰 널빤지로 만드는 것을 숨기는 함정이 존재하고 있습니다.

4. 문제를 풀기 위한 핵심 아이디어

이번 문제는 매 순간 가장 빈도가 낮거나 작은 두 개의 노드를 결합하여 트리 형태로 묶어 올라가는 최적화 방식을 컴퓨터 공학에서는 허프만 코딩(Huffman Coding) 알고리즘이라고 합니다.

이 문제는 필요한 널빤지들에서 작은 것들을 합쳐서 최종적으로 큰 널빤지로 만드는 것으로 해결할 수 있으며, 이 과정에서 우선순위 큐가 사용됩니다. 구체적인 방법은 다음과 같습니다.

1. 필요한 널빤지들의 길이를 우선순위 큐에 넣어줍니다.
2. 우선순위 큐에서 가장 작은 값 두 개를 뽑아 더해줍니다.
3. 더해준 값은 최종 결과 값에 누적시켜 주고, 우선순위 큐에 다시 추가해 줍니다.
4. 우선순위 큐에 값이 하나만 남을 때까지 위 과정을 반복해 줍니다.

그럼 위 과정대로 “예제2”로 진행해 보도록 하겠습니다.

• 초기 상태: [1, 2, 3, 4, 5] (현재 가장 작은 두 개: 1, 2)

• 1단계: 1과 2를 합칩니다.
  • 발생 비용: 3
  • 합친 값을 우선순위 큐에 다시 넣어 줍니다.
  • 현재 남은 조각: [3, 3, 4, 5]
• 2단계: 남은 조각 중 가장 작은 두 개인 3과 3을 합칩니다.
  • 발생 비용: 6
  • 합친 값을 우선순위 큐에 다시 넣어 줍니다.
  • 현재 남은 조각: [6, 4, 5]
• 3단계: 남은 조각 중 가장 작은 두 개인 4와 5를 합칩니다.
  • 발생 비용: 9
  • 합친 값을 우선순위 큐에 다시 넣어 줍니다.
  • 현재 남은 조각: [6, 9]
• 4단계: 남은 조각 6과 9를 합칩니다.
  • 발생 비용: 15
  • 우선순위 큐에 값이 하나만 남았으므로 루프를 종료합니다.
• 총 누적 비용: 3 + 6 + 9 + 15 = 33

그렇다면 이 과정을 합쳐나가는 것이 아닌 자르는 과정으로도 한 번 보도록 하겠습니다.

• 15를 6과 9로 나누어 줍니다. 이 과정에서 비용은 15 발생합니다.

• 9를 4와 5로 나누어 줍니다. 이 과정에서 비용은 9 발생합니다.

• 6을 3과 3으로 나누어 줍니다. 이 과정에서 비용은 6 발생합니다.

• 3을 1과 2로 나누어 줍니다. 이 과정에서 비용은 3 발생합니다.

• 발생한 비용 3, 6, 9, 15를 모두 합하면 33이 됩니다.

하지만 큰 값에서 자르는 것은 자를 땐 최적으로 자르는 기준을 정할 수가 없다는 문제가 존재하여 큰 수에서 자르는 방식으로는 이 문제를 풀 수 없습니다.

마지막으로 우선순위 큐를 이용한 코드는 다음과 같습니다.

import sys
import heapq

input = sys.stdin.readline

n = int(input())

# heapq는 일반 리스트를 우선순위 큐처럼 다룹니다.
queue = []

for _ in range(n):
    num = int(input())
    heapq.heappush(queue, num)

result = 0

# 큐에 원소가 1개 남을 때까지 반복
while len(queue) > 1:
    
    # 가장 작은 값 두 개를 뽑음 (get 대신 heappop 사용)
    num1 = heapq.heappop(queue)
    num2 = heapq.heappop(queue)
    
    sum_value = num1 + num2
    result += sum_value
    
    # 합친 값을 다시 큐에 넣음 (put 대신 heappush 사용)
    heapq.heappush(queue, sum_value)

print(result)

5. 우선순위 큐를 이용한 그리디 알고리즘 유형을 잘 알아볼 수 있는 방법

우선순위 큐를 이용해야 하는 문제들은 다음과 같은 동작 트리거를 완벽하게 공유합니다.

1. 트리거 A(동적 변화): 배열의 데이터가 고정되어 있지 않다. 두 개를 뽑아서 무언가 연산을 한 뒤, 새로 만들어진 데이터가 다시 배열로 들어간다.

2. 트리거 B(극값의 연속 추출): 그런데 그 요동치는 배열 안에서 지속적으로 ‘가장 작은 값(또는 가장 큰 값)’을 계속 찾아내야 한다.

일반적인 배열 정렬(Sort)은 데이터가 고정되어 있을 때 한 번만 쓰면 되지만, 데이터가 계속 추가되고 빠지는 ‘동적’인 상황에서 $O(\log N)$의 속도로 최솟값을 계속 뽑아낼 수 있는 자료구조는 컴퓨터 공학에서 우선순위 큐(Heapq)가 유일합니다.