[백준] 1715번 : 카드 정렬하기

유형 : 힙, 자료구조, 그리디

 

[예제 입력]

3
10
20
40

[예제 출력]

100

---

1. 아이디어

처음에 예제를 잘못 이해했다.

2개씩 묶어서 결국 가장 적은 비교 횟수를 구하고자 하기 위해 작은 크기부터 정렬을 해야 한다고 생각했다. 여기까지는 방향을 맞게 왔으나.. 카드 묶음을 비교하고 난 결과값을 다시 카드 더미에 넣는 부분을 빼먹었다.

그래서 테스트케이스 값이 계속 다르게 나와 어디서 틀린지조차 몰랐었다.

 

알고리즘은 다음과 같다. (풀이 참고)
① 총 비교 횟수(result)를 0으로 둔다.
② 현재 카드 더미(card) 중 가장 작은 2개의 카드 묶음(first, second)을 고른다.
③ _sum = first + second 값이 현재 단계에서 비교한 횟수를 의미한다.
④ _sum 값을 총 비교 횟수(result)에 더한다.
⑤ _sum 값을 다시 카드 더미(card)에 넣는다.
⑥ 위의 과정을 반복해 힙에 하나의 덱만 남으면 멈춘다. 

 

ex) 30 40 50 60 → 360

문제에서 주어진 예시 외에 추가적인 테스트 케이스를 원한다면 아래 링크를 참고하면 된다.

https://www.acmicpc.net/board/view/72799

 

 

2. 풀이

1) 첫 번째 풀이(틀림)

import sys
n = int(sys.stdin.readline())

if n == 1:
    print(0)
else:
    arr = []
    for _ in range(n):
        arr.append(int(sys.stdin.readline()))

    arr = sorted(arr)

    sum1 = arr[0] + arr[1]
    sum2 = sum1
    for i in range(2, n):
        sum1 += arr[i]
        sum2 += sum1

    print(sum2)

애초에 문제 자체를 이해를 못해서 풀이가 틀렸었다. 그리고 검색해보니, 이런 식으로 했어도 시간 초과가 나왔을 것 같다.

 

2) 두 번째 풀이

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

if n == 1:
    print(0)
else:
    for _ in range(n):
        heapq.heappush(heap, int(input()))

    result = 0
    while len(heap) > 1:
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        _sum = first + second
        result += _sum
        heapq.heappush(heap, _sum)

    print(result)

최소 힙을 사용해서 풀면 간단하게 해결할 수 있는 문제였다. 위의 알고리즘을 보면, 코드가 금방 이해가 될 것이다.

 

---

문제 출처

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

 

풀이 참고

1) https://claude-u.tistory.com/341

2) 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online