백준 15903 카드 합체 놀이 Python 3

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

15903번: 카드 합체 놀이

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ15903.py

import sys, heapq
def union_cards(cards, m):
    while m > 0:
        nsum = heapq.heappop(cards) + heapq.heappop(cards)
        m -= 1
        heapq.heappush(cards, nsum)
        heapq.heappush(cards, nsum)
    print(sum(cards))
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))
heapq.heapify(cards)
union_cards(cards, m)

---

풀이 과정

• 첫 번째 코드

m번 카드 합체를 진행하는데 매번 오름차순 정렬을 한 후, 가장 작은 카드 두 개를 합치는 방식으로 진행했다.

이 문제의 경우 입력 n이 최대 1000이기 때문에 시간 초과는 발생하지 않으나, 시간복잡도는 O(m*n log n)이다.

import sys
def union_cards(cards, m):
    while m > 0:
        cards.sort()
        m -= 1
        nsum = cards[0] + cards[1]
        cards[0] = cards[1] = nsum
    print(sum(cards))
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))
union_cards(cards, m)

 

• 두 번째 코드

heap 자료구조를 이용하였다.

pop 연산은 O(1)이 소요되고, push 연산은 힙 구조 재정렬하는데 걸리는 O(log2 n)이 소요된다.

따라서 시간복잡도가 O(m log2 n)이다.

import sys, heapq
def union_cards(cards, m):
    while m > 0:
        nsum = heapq.heappop(cards) + heapq.heappop(cards)
        m -= 1
        heapq.heappush(cards, nsum)
        heapq.heappush(cards, nsum)
    print(sum(cards))
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))
heapq.heapify(cards)
union_cards(cards, m)

 

시간이 거의 2배나 차이가 난다. 복잡도를 고려해서 유리한 자료구조를 선택하는 것이 중요하다!