[백준] 15903 : 카드 합체 놀이 - Python(파이썬)

[Silver 2] 15903 : 카드 합체 놀이 - Python

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

---

풀이

입력받은 숫자 리스트를 먼저 정렬한 후, 가장 작은 수 2개 (첫번째, 두번째)를 더한 값을
다시 첫번째 두번째 인덱스의 값으로 할당한 후 다시 정렬한다
이 과정을 반복하여 최종 결과값을 출력한다

 

n, m = map(int, input().split())
num_data = [int(x) for x in input().split()]

num_data.sort() # 오름차순으로 정렬


for i in range(m):
    val = num_data[0] + num_data[1] # 가장 작은 두 값을 더한다
    num_data[0], num_data[1] = val, val # 더한 값을 다시 할당
    num_data.sort() # 다시 정렬

print(sum(num_data))

파이썬의 sort 함수의 시간복잡도가 O(nlogn) 인데,

이 문제에서 Heapsort를 사용하면 O(logn)으로도 해결 할 수 있다.