[그리디] 코딩테스트 문제 TIL (카드 합체 놀이) - 백준 15903번

말하는 감자·2024년 12월 30일

TIL algorithm baekjoon greedy heap priority queue python 그리디 백준 알고리즘 우선순위 큐 코딩테스트 코딩테스트 준비 파이썬 힙

코딩테스트 유형별 풀이

목록 보기

63/67

이번 문제는 카드 정렬하기 문제와 매우 유사합니다. 같이 비교하면서 풀면 좋을것 같습니다.

1. 오늘의 학습 키워드

그리디
우선순위 큐
힙

2. 문제: 15903. 카드 합체 놀이

단계: 🥈 실버 1단계
주제:
출처: https://www.acmicpc.net/problem/15903

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

3 1
3 2 6

예제 출력 1

예제 입력 2

4 2
4 2 3 1

예제 출력 2

3. 문제 풀이

Step1. 문제 이해하기

주어진 문제는 카드 합체 과정을 반복하면서 카드 숫자의 합을 최소화하는 문제입니다.

입출력은 다음과 같습니다:

Input:
- 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어집니다.
- 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어집니다. (1 ≤ ai ≤ 1,000,000)
Output:
- 만들 수 있는 가장 작은 점수를 출력합니다.

Step2. 문제 분석하기

이 문제의 정답은 문제에 다 나와있습니다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수의 최솟값이 목표입니다.

그렇다면 n장의 카드에서 매번 가장 작은 값들을 더해서 새로운 값으로 배정하면 되지 않을까요?

이렇게 합하고 다시 배정하려면 우선순위 큐를 사용하면 쉽게 해결할 수 있습니다.

방법을 정리하자면 다음과 같습니다:

1. 우선순위 큐 (힙) 사용

카드 숫자를 작은 값 순서로 정렬하고, 두 개의 가장 작은 값을 선택하여 합쳐야 하므로 우선순위 큐(최소 힙)를 사용하면 효율적으로 처리할 수 있습니다.
Python의 heapq 모듈을 사용하여 최소값을 빠르게 선택하고, 합친 값을 다시 힙에 삽입합니다.

2. 카드 합체 과정

초기 카드 값을 힙에 삽입합니다.
m번 반복하며:
- 힙에서 가장 작은 두 값을 꺼냅니다.
- 두 값을 더한 결과를 다시 두 번 힙에 삽입합니다.
m번의 합체가 끝나면 힙에 남은 모든 값의 합을 계산합니다.

3. 최적화

힙 자료구조를 사용하여 최소값 선택과 삽입 작업을 효율적으로 수행합니다. 각 작업은 $O(\log n)$ 시간이 걸리며, 최대 m번의 작업이 필요합니다.

Step3. 코드 설계

입력을 처리하고, 초기 카드 배열을 힙에 삽입합니다.
카드 합체를 m번 수행하며:
- 힙에서 최소값 두 개를 꺼내 합친 값을 계산합니다.
- 합친 값을 다시 두 번 힙에 삽입합니다.
최종적으로 힙에 남은 모든 값을 더하여 출력합니다.

Step4. 코드 구현

import sys
from heapq import heappop, heappush, heapify
n, m = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
def sol(m, cards):
    heapify(cards)
    for _ in range(m):
        x = heappop(cards)
        y = heappop(cards)
        new_val = x + y
        heappush(cards, new_val)
        heappush(cards, new_val)
    return sum(cards)
print(sol(m=m, cards=cards))

코드 설명: 1. heapify로 초기화
- heapq.heapify(cards)를 통해 입력 배열을 최소 힙으로 변환합니다.
- 최소값 두 개를 효율적으로 꺼내기 위해 힙 자료구조를 사용합니다.
  
  2. 카드 합체 과정
- heapq.heappop(cards)로 힙에서 최소값 두 개를 꺼냅니다.
- 합친 값을 다시 두 번 힙에 삽입합니다.
  
  3. 최종 점수 계산
- 카드 합체가 끝난 후, 힙에 남은 모든 값을 더하여 점수를 계산합니다.
시간 복잡도:
1. 힙 작업:
  - 힙 삽입 및 삭제 작업은 $O(\log n)$ 시간 복잡도를 가집니다.
  - m번의 합체 작업이 필요하므로 전체 복잡도는 $O(m \log n)$ 입니다.
2. 점수 계산:
  - 점수 계산은 힙의 모든 요소를 순회하며 합을 구하므로 $O(n)$ 입니다.
  
  3. 최종 복잡도:
  
  $O(m \log n + n), n, m$ 이 최대 $10^4$ 까지 가능하므로 효율적으로 동작합니다.
결과:

4. 마무리

이번 문제는 그리디 알고리즘과 우선순위 큐를 활용하여 해결할 수 있는 대표적인 문제였습니다. 핵심은 매번 가장 작은 두 값을 합치고 다시 정렬하는 과정을 효율적으로 수행하기 위해 최소 힙 자료구조를 사용하는 것이었습니다. 카드 합체 과정을 반복적으로 수행한 후, 힙에 남은 모든 값을 더하여 최소 점수를 계산했습니다. Python의 heapq 라이브러리를 사용해 구현하였고, 시간 복잡도는 $O(m \log n + n)$ 로 매우 효율적이었습니다. 이 문제를 통해 우선순위 큐를 활용한 그리디 알고리즘의 중요성을 다시 한번 느낄 수 있었습니다.