[백준] 15903 카드 합체 놀이

백준 15903 카드 합체 놀이 문제 바로가기

 

카드 합체 놀이는 가지고 있는 카드 모음(자연수로 이루어진 배열)중에서 2장의 카드 1) x, y를 뽑고 2) 뽑은 2장의 카드를 각각 x+y값으로 변환시키는 과정을 문제에 주어진 합체 가능 횟수만큼 반복하는 게임이다. 이 게임을 진행하며 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 구현하는 것이 목적이다.

주어진 예제를 가지고 문제 이해하기

문제에서 주어진 예제 중 맨 처음 카드 상태가 4 2 3 1인 예제 가지고 문제에서 해결법을 찾아보자. 해당 예제는 카드 합체를 2번 수행한다. 먼저, 해당 숫자 배열에서 뽑을 수 있는 2개의 숫자 종류는 아래와 같다.

 

(4,2), (4,3), (4,1), (2,3), (2,1), (3,1)

 

각 케이스의 숫자들이 뽑혔다고 가정하고 전체적인 흐름을 적어보겠다.

 

4,2,3,1 -> 4,2를 선택 -> 6,6,3,1 -> 3,1을 선택 -> 6,6,4,4

4,2,3,1 -> 4,3을 선택 -> 7,2,7,1 -> 2,1을 선택 -> 7,3,7,3

4,2,3,1 -> 4,1을 선택 -> 5,2,3,5 -> 2,3을 선택 -> 5,5,5,5

4,2,3,1 -> 2,3을 선택 -> 4,5,5,1 -> 5,1을 선택 -> 4,5,6,6

4,2,3,1 -> 2,1을 선택 -> 4,3,3,3 -> 3,3을 선택 -> 4,3,6,6

4,3,2,1 -> 3,1을 선택 -> 4,4,2,4 -> 2,4를 선택 -> 4,4,6,6

 

이렇게 적어놓고 유심히 살펴보니 신기한 규칙을 발견했다.

첫번째 케이스인 4,2,3,1 -> 4,2를 선택 -> 6,6,3,1 -> 3,1을 선택 -> 6,6,4,4를 예시로 봐보면 아래와 같은데

 

(1) 4,2,3,1의 총 합 = 10

(2) 4,2의 합 = 6

(3) 6,6,3,1의 합 = 16 (10+6)

(4) 3,1의 합 = 4

(5) 6,6,4,4의 합 = 20 (16+4)

 

기존 배열(1)의 총 합에 고른 2개의 수(2)를 뽑아서 더하면 카드 합체를 수행한 배열(3)의 총 합이 되고, 거기서 또 2개의 수(4)를 뽑아서 이전 배열(3)의 총 합에 더하면 카드 합체를 수행한 배열의 총 합(5)이 된다.

 

이 규칙을 바탕으로 코드를 작성하였고, 테스트에 통과하여 맞았습니다를 받았다.

import sys
input=sys.stdin.readline

n, m = map(int, input().split())
cards = sorted(list(map(int, input().split())))

for _ in range(m):
    a, b = cards[0], cards[1]
    cards[0], cards[1] = a+b, a+b
    cards = sorted(cards)

print(sum(cards))

 

코드 개선하기

이 풀이도 맞지만, 이것보다 시간을 더 효율적으로 사용할 수 있는 풀이가 있었다. 우선순위 큐인 heapq를 사용하는 방법이었다.

내가 작성한 코드는 카드 2개를 고르고 다시 합체를 수행한 뒤 배열을 매번 sort() 과정을 수행하기때문에 O(nlogn)의 시간복잡도를 가져야했는데, heapq를 사용한다면 sort()를 사용하지 않고도 heappush를 통한 삽입으로 O(logn)의 시간복잡도로 만들 수 있었다.

 

import sys
import heapq
input=sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))

# 이미 원소가 들어있는 리스트를 힙구조로 만들어준다.
heapq.heapify(cards)

for _ in range(m):
    # 최소힙 형태이므로 heappop을 이용해 최소값 2개를 순차적으로 pop해준다.
    card1 = heapq.heappop(cards)
    card2 = heapq.heappop(cards)
    
    # heappush를 이용해 합체한 카드를 다시 힙에 넣어준다.
    # heappush로 값을 넣으면 알아서 다시 힙 형태로 정렬된다.
    heapq.heappush(cards, card1 + card2)
    heapq.heappush(cards, card1 + card2)

print(sum(cards))

 

236ms -> 56ms로 시간을 확 단축시킬 수 있었다.