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

0.  문제 링크

 

 

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

1715번: 카드 정렬하기

---

1.  풀이 방법

 

 

이 문제는 감이 중요할 것 같은 문제이다.

행렬의 곱셈 연산에서 생각했을 때, DP로 풀어야 될 것 같지만 정답은 그리디로 풀어야 하는 문제이다.

 

아래의 코드에서 써놓았는데, i < j < k라고 가정했을 때, 최소 연산은 당연히도 (i + j) + (i + j + k) = 2 * (i + j) + k이다.

i + k를 먼저 수행한다면, 2 * (i + k) + j가 될 것이다. 부등식을 푼다면 내가 말한 방법이 더 적게 든다는 것을 알 수 있다.

이 방법은 i < j < k < h일 때, i + j가 h보다 클 때도 적용된다.

이렇게 되면 k < h < i + j가 되므로, 이때는 k + h를 먼저 수행하면 된다.

 

이제 감이 잡혔을 것 같은데, 이 문제는 우선순위 큐와 그리디를 사용해서 풀면 된다.

 

1. 입력을 우선순위 큐에다가 넣는다.
2. 작은 두 개를 빼내서 더한 후, 연산 횟수를 기록한다. 더한 값은 다시 우선 순위 큐에 넣는다.
3. 이를 반복한다.
4. 최종적으로 힙에 하나의 숫자가 남았을 때 종료한다.

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    maps = list()
    for _ in range(n):
        heapq.heappush(maps, int(input()))      # 작은 애들끼리 더하는게 맞음

    """
    i, j, k >>> i < j < k
    i + j + (i + j + k) = 2 * (i + j) + k
    """

    ans = 0
    while len(maps) > 1:
        x = heapq.heappop(maps)
        y = heapq.heappop(maps)
        ans += x + y

        heapq.heappush(maps, x + y)
        
    print(ans)

---

3.  마무리