[Python] 백준 1715 카드 정렬하기 | 그리디 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1715번: 카드 정렬하기

 

 

문제 해결 포인트

- 작은 카드 뭉치들 부터 순서대로 처리해야 하므로 그리디 알고리즘입니다!

- 카드 뭉치가 1개라면 비교할 뭉치가 없으므로 0 반환

- 카드 뭉치가 3개 이상이라면 최소값 2개를 뽑아 순서대로 연산(우선순위 큐)

- 큐 안에 뭉치가 2개 남았다면 더이상 최소 값 2개를 찾지 않고 연산 값을 더하여 출력 & 반복문 종료

 

작성 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())  # 뭉치 개수
nums = []  # 우선순위 큐
result = 0

for _ in range(n):
    heapq.heappush(nums, int(input()))  # 각 카드 뭉치 우선순위 큐 삽입

if len(nums) == 1:  # (주의) 카드 뭉치가 1개라면 비교할 것이 없으므로 0 반환
    print(0)
else:  # 2개 이상의 카드 뭉치가 있다면
    while nums:  # 카드 뭉치가 있을 동안
        if len(nums) == 2:  # 뭉치가 2개라면 최소 개수를 가지는 뭉치를 찾지 않아도 된다
            print(result + sum(nums))  # 결과 출력 후 반복문 종료
            break
        temp = heapq.heappop(nums) + heapq.heappop(nums)  # 남은 뭉치 중 최소 값 2개 합
        heapq.heappush(nums, temp)  # 우선순위 큐 삽입 
        result += temp  # 연산 횟수 합산

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚