링크


문제 요약:  주어진 조건을 이용하여 모든 카드의 숫자 합이 최솟값으로 만들기

문제 해결 방안: 매번 가장 작은 2개의 수를 골라서 연산하기 

문제 해결 키워드: heap 사용 해보기 


2개의 수를 골라서 더한값을 덮어 써야 하므로 

최솟값을 만들려면  항상 배열의 가장 작은 2개의 값을 골라 더하고 더한값을 바꿔야 한다.

이때 매번 sort 를 사용하면 오래 걸릴 수 있으므로 

heap을 사용하여 정렬없이 알아서 작은 값 2개를 뽑는 과정이 필요하다 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
 
# 입력 받기 
n,m=map(int,input().split())
st=list(map(int,input().split()))
 
def solution(m,st):
    # 한번 정렬해주기 
    st.sort()
    for _ in range(m):
        # 2개 가장 작은수 2개를 빼고 더하기
        x_y=heapq.heappop(st)+heapq.heappop(st)
        # 고른 2개의 수를 바꿔줘야함
        heapq.heappush(st,x_y)
        heapq.heappush(st,x_y)
    
    # 다했으면 최솟값 가져오기
    return sum(st)
 
# 정답 출력하기
print(solution(m,st))
cs






p.s  제출하기 전에 


heapq.heappop(st) 하면 알아서 최솟값을 뽑는걸로 알고있는데

돌려봐도 계속 작은놈이 안나와서  반복문 전에 딱 한번만 sort 로 정렬해서 풀었음

여기 게이들은 나보단 30만배는 잘하니까 sort 명령어 없이 잘 풀 수 있을거라 생각함