[BOJ] Python 백준 15903번 카드 합체 놀이 실버 2

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

15903번: 카드 합체 놀이

 

문제 풀이

---

문제 설명이 길지만 간단하게 요약하자면 입력받은 m번만큼 가장 작은 두 개의 카드 숫자를 더해서 갱신을 반복하는 것이다.

 

m번의 반복이 끝난 뒤 모든 카드의 합을 가장 작게 만드는 것이 목표이므로 매순간 가장 작은 카드 두개를 선택하여 갱신하는것을 파악하는게 가장 중요한 문제같다.

 

이 문제를 푸는 방법으로 생각난 것은 그리디 알고리즘과 최소 힙이며 두 가지 모두 구현해보았다.

 

n이 최대 1000이고 m은 최대 15000이므로 그리디 알고리즘을 사용하여 매번 갱신하면 약 15000 X 5000(1000*log1000) = 75000000 (7천 5백만)의 연산 횟수가 나오므로 약간 간당간당할꺼 같다고 생각했지만 결과적으론 통과하였다.

 

우선 그리디 알고리즘은 m번을 반복하면서 계속 리스트를 오름차순 정렬하여 가장 작은 두 개를 갱신하는 방식이고 최소 힙은 자체에서 가장 작은 원소를 뽑아내는 효율적인 알고리즘을 갖고 있기에 단순하게 원소 두 개를 뽑고 합을 두 번 넣어주면 해결할 수 있다.

 

당연하게도 오름차순 정렬할 땐 O(nlogn)의 시간 복잡도가, 최소 힙은 정렬 시 O(logn)의 시간 복잡도가 걸리기 때문에 최소 힙을 사용하는게 더 효율적인 방식이다.

 

전체 코드를 보면서 설명하겠다.

 

그리디 알고리즘 코드

---

n,m=map(int,input().split())
card=list(map(int,input().split()))
for i in range(m):
    card.sort()
    card[0],card[1]=card[0]+card[1],card[0]+card[1]

print(sum(card))

 

1, 2 번째 줄은 n과 m, card 리스트를 입력받았다.

 

그리고 m번 반복하면서 card 리스트를 정렬하고 가장 작은 두 개를 갱신한 뒤 전체 합을 출력하면 된다.

 

이때 주의해야 할점은 말했듯이 매번 정렬을 해야 한다는 점인데 그 이유는 가장 작은 두 개의 숫자를 더해서 갱신했을 때 해당 숫자들이 전체 리스트에서 가장 작은 두 개의 숫자라는 보장이 없기 때문이다.

 

이렇게 매번 O(nlogn)의 시간 복잡도가 걸려서 갱신해야 되기 때문에 보다 비효율적인 방식이다.

 

다음은 최소 힙을 이용한 코드이다.

 

최소 힙 코드

---

 

import heapq

n,m=map(int,input().split())
card=list(map(int,input().split()))
heapq.heapify(card)
for i in range(m):
    tempa=heapq.heappop(card)
    tempb=heapq.heappop(card)
    heapq.heappush(card,tempa+tempb)
    heapq.heappush(card,tempa+tempb)

print(sum(card))

 

먼저 힙 모듈을 사용하기 위해 heapq를 import 했고 n, m, card 리스트를 입력받는 부분까진 똑같다.

 

5번째 줄의 heapify는 기존의 리스트를 heap 형태로 변환하는 함수이다.

 

그리고 6번째 줄부터는 m번 반복하면서 두 번 숫자를 뽑고 더한값을 다시 두 번 넣어준다.

 

마찬가지로 sum 함수를 이용해 전체 합을 출력하면 된다.

 

그리디 알고리즘이랑은 다르게 매번 갱신 시 O(logn)의 시간복잡도가 걸리므로 더 효율적인 코드인 것을 알 수 있다.

 

결과 화면

결과화면에서 확인할 수 있듯이 실제로도 시간에서 차이가 났다.

 

같은 문제를 풀더라도 방식에 따라 효율성에서 차이가 나므로 항상 효율적인 방법을 고민하는게 중요한 것 같다.