Baekjoon Training #1715

---

#1715 카드 정렬하기

import heapq
import sys
input = sys.stdin.readline

n=int(input())
cards = [int(input()) for _ in range(n)]
heapq.heapify(cards)    # cards 리스트를 힙으로 바꿔주는 함수
ans = 0        # 결과의 초기값을 0으로 설정

while len(cards) > 1:   # cards 리스트의 길이가 1보다 클때 연산을 진행
    tmp = heapq.heappop(cards) + heapq.heappop(cards)   # 최소값 두개의 합을 tmp에 저장하고
    heapq.heappush(cards, tmp)      # 해당 tmp값을 heap에 넣음
    ans += tmp      # 정답에 tmp값을 더해나감
    
print(ans)

이 문제에서의 핵심은 세가지가 존재한다.

1. 누적합의 개념을 이용하기에 적합한 자료형인 우선순위 큐를 구현하기 위해 힙을 이용하는 것이다.

2. 누적합을 활용할때는 합을 담아둘 임시변수를 만들어두고 연산을 반복하며 변수 값을 바꿔주는 것이 핵심이다.

3. 무조건적으로 최소값 두개를 찾아서 그 숫자끼리 더하고 더한 값도 힙에 다시 넣어 최소값 조사에 반영한다는 알고리즘이 필요하다.

 

발표준비를 하기위해 두가지 코드를 추가로 첨부한다. 두코드 모두 시간초과로 이용불가능한 코드이다.

 

sort()이용 코드

import sys
input = sys.stdin.readline

n=int(input())
cards = [int(input()) for _ in range(n)]
cards.sort()   # cards 리스트를 오름차순으로 정렬하는 함수
ans = 0        # 결과의 초기값을 0으로 설정

while len(cards) > 1:   # cards 리스트의 길이가 1보다 클때 연산을 진행
    tmp = cards[0] + cards[1]   # 최소값 두개의 합을 tmp에 저장하고
    cards = [tmp] + cards[2:]   # 해당 tmp값을 리스트 맨 앞에 넣음
    cards.sort()   # 리스트를 다시 정렬함
    ans += tmp      # 정답에 tmp값을 더해나감
    
print(ans)

 

min()이용 코드

n = int(input())
cards = [int(input()) for _ in range(n)]

while len(cards) > 1:
    min1 = min(cards)
    cards.remove(min1)
    min2 = min(cards)
    cards.remove(min2)
    tmp = min1 + min2
    cards.append(tmp)

print(cards[0])

---