[Python] 백준 15903번 카드 합체 놀이

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

15903번: 카드 합체 놀이

| 문제 내용

n개의 숫자 카드 중 가장 작은 수 두개를 더해서 각각 덮어 씌우는 행동을 m 번 반복했을 때 전체 숫자 카드의 합계가 최소인 값 구하기 

 

| 풀이

더하기 전 매번 정렬을 통해 가장 작은 수 2개를 정할 수도 있지만 이 방법은 O(n)의 시간복잡도가 소요됨.

배열 정렬대신 우선순위큐를 사용하면 O(logn)의 시간으로 작은 수를 구할 수 있음.

 

import sys, heapq
input = sys.stdin.readline

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

# 우선순위큐를 사용하는 게 속도 측면에서 좋음
heapq.heapify(num_list) # 리스트를 힙으로 변경

for i in range(m):
    x = heapq.heappop(num_list)
    y = heapq.heappop(num_list)

    heapq.heappush(num_list, x + y)
    heapq.heappush(num_list, x + y)

print(sum(num_list))

 

| 느낀점

무작정 풀지말고 효율적인 구조를 먼저 생각하고 풀자