[이코테] 그리디 - 카드 정렬하기

1. 문제

• 백준 1715와 동일한 문제
  • 링크

입출력 예시

2. 아이디어

• 매순간 가장 작은 두수를 뽑아서 더하고 그 수를 누적한다. (두 수의 합이, 뽑히는 수가 된다)
• heapq 자료구조를 이용하고, 자료구조안에 원소가 1개가 남을때까지 반복한다.

3. 예제코드

import sys
input = sys.stdin.readline
import heapq

# 입력 
n = int(input())

nums = []
for _ in range(n):
    heapq.heappush(nums, int(input()))
    
cum = 0    
while len(nums) > 1:
    first = heapq.heappop(nums)
    second = heapq.heappop(nums)
    
    sum_fs = first + second   # 가장작은 둘을 꺼내서 더한다.
    cum += sum_fs    # 그것을 누적한다.
    
    heapq.heappush(nums, sum_fs)   # 가장작은 둘을 꺼낸 결과를 다시 우선순위 큐에 넣는다. 
    
print(cum)

4. 배운점

• heapq 사용 리마인드

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬