자발적으로 우선순위큐라는 자료구조를 생각해낸 풀이!

1. 내 풀이: 실패 ()

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = list(map(int, input().split()))
heap = []

for i in nlist:
    heapq.heappush(heap, i)
    
for _ in range(m):
    temp = heap[0] + heap[1]
    heap[0] = temp
    heap[1] = temp  

print(sum(heap))

80%로 성공이라고 할래 ㅠㅠ ...
처음에 테스트 케이스 다 통과해서 제출해보자! 했는데 자꾸

환장 ,,, 그래서 답이랑 무엇이 틀릴까나 하고 봤더니 두번째 for문이 틀렸었다.
일단 우선순위큐를 이용해서 최솟값들이 제일 앞에 배치될 것이므로 [0], [1]을 당연히 뽑았는데,
temp 값을 다시 저렇게 저장해주면

두 번째 테스트 케이스의 경우 이렇게 결과가 나오게 된다.
즉 우선순위큐를 쓰는 이유가 없어지는 것 ...

이 부분은

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = list(map(int, input().split()))
heap = []

for i in nlist:
    heapq.heappush(heap, i)
    
for _ in range(m):
    x = heapq.heappop(heap)
    y = heapq.heappop(heap)
    heapq.heappush(heap, x+y)
    heapq.heappush(heap, x+y)    

print(sum(heap))

우선순위큐를 쓰기 때문에 동일한 의미가 되어 내가 원하던 결과가 나오게 된다.

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))

풀이 출처: https://ralp0217.tistory.com/entry/%EB%B0%B1%EC%A4%80Python15903%EB%B2%88-%EC%B9%B4%EB%93%9C-%ED%95%A9%EC%B2%B4-%EB%86%80%EC%9D%B4Greedy

기억하고 가야할 것!
heapify를 통해 list를 바로 heap으로 구현할 수 있다.

3. 마치며

오랜만의 알고리즘 ... 아픈 상태로 풀어서 글자가 꼬부랑뱅이였지만 ㅠㅠ
그래도 내가 80%로는 풀어서 뿌듯하다!