[백준] 1715 카드정렬하기

문제

---

풀이 과정

1) 문제 이해 및 접근

가장 작은 수들을 우선으로 더해주면 되므로 그리디로 접근했습니다.

연산한 수를 리스트에 다시 넣고 그 중 가장 작은 수를 다시 빼서 사용해야 하므로 최소 힙을 사용했습니다.

2) 알고리즘

• 그리디 알고리즘
• 최소 힙

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')


N = int(sys.stdin.readline())   # 숫자 개수
heap = []                       # 힙으로 사용할 리스트
answer = 0                      # 정답 변수

for _ in range(N):              # 숫자들을 모두 최소힙에 푸시
    heapq.heappush(heap, int(sys.stdin.readline()))

while len(heap) > 1:                        # 최소힙 안에 2개 이상 있으면 반복
    node_1 = heapq.heappop(heap)            # 가장 작은 수
    node_2 = heapq.heappop(heap)            # 두번째로 작은 수
    answer += node_1 + node_2               # 정답에 더함
    heapq.heappush(heap, node_1 + node_2)   # 더한 수를 최소힙에 추가

print(answer)

---

결과 및 학습한 내용

1) 어려웠던 내용

규칙을 발견하는데 어려움이 있었습니다.

연산한 결과를 다시 리스트에 넣고 그 중 가장 작은 수 2개를 찾아서 다시 연산 해야했는데, 특수한 케이스가 있을거라는 생각에 시간이 더 많이 소요되었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

문제 링크

- https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다