[백준,Python]15903번 카드 합체 놀이(Greedy)

[백준,Python]15903번 카드 합체 놀이(Greedy)

www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

이번 문제의 알고리즘은 Greedy이고, 1. 처음 푼 풀이와 2. 효율적인 풀이를 비교하며 설명하려고 한다. 

 

 

1. 처음 푼 풀이

import sys
input = sys.stdin.readline

a,b = map(int, input().split())
card  = list(map(int,input().split()))

for i in range(b):
    card = sorted(card)
    cover = card[0] + card[1]
    card[0] = cover
    card[1] = cover

print(sum(card))

-다음과 같이 비교적 간단하게 생각할 수 있는 풀이 방법이다. m번 합체할 때 마다 정렬 해주고, 인덱스 기준 0, 1을 연산값으로 바꿔주는 알고리즘으로 풀게 되었다. 반복문 안에서 sort를 하게 될 경우 다시 넣을 때마다 sort 함수를 작동 시키므로 시간복잡도는 O(nlogn)이 된다. 그래도 요구하는 식이 복잡하지 않아 간단하게 구현하여 정답을 내게 되었다.

 

 

2. 효율적인 풀이 

import sys
import heapq
input = sys.stdin.readline

n,m = map(int, input().split())

card = list(map(int,input().split()))
heapq.heapify(card)

for i in range(m):
    card1 = heapq.heappop(card)
    card2 = heapq.heappop(card)

    heapq.heappush(card, card1+card2)
    heapq.heappush(card, card1 + card2)
print(sum(card))

-heap으로 구현한 우선순위 큐를 사용하게 되면 카드 2개를 뽑을 때 마다 정렬하는 것이 아니라 heappop()를 통해 값을 빼주기만 하고 다시 heappush()만 하면 되기에 오히러 더 간단하게 풀 수 있었다. 자료구조 heap에서 삽입연산의 시간 복잡도는 O(logn)이다. 첫번째 풀이보다 훨신 효율적이다는 것을 알 수 있었다. 

 

 

두 풀이에 시간을 비교해보면 다음과 같은 결과를 확인할 수 있었다.

위: 우선 순위 큐 이용 / 아래 : sort이용.