백준 1082 - 방 번호

1082번: 방 번호 (acmicpc.net)

1082번: 방 번호

 

이번주에 알고리즘 공유 문제는 방 번호 문제이다.

이 문제는 dynamic programming과 Greedy Algorithm을 모두 떠올려야하는 문제로 점화식 작성을 할 때 Greedy를 생각하지 않으면 쉽사리 작성할 수 없는 문제이다.

 

문제를 먼저 이해해보자.

 

예제 입력 1 복사

3
6 7 8
21

예제 출력 1 복사

210

 

이렇게 6 7 8 을 입력받게 될 때 방 번호는 각각 0 1 2가 될 것이다.

 

방 가격 : 6 7 8

방 번호 : 0 1 2 

 

이런 모습이 나오게 되는데 여기서 최대 금액이 21원이 넘지 않는 최댓값을 탐색해야하므로, 방 뒷번호 부터 차례대로 합을 계산해볼 수 있다. 8 + 7 + 6 = 21이므로, 정확히 맞아 떨어지게 되고, 값은 방번호를 나열한 210으로 출력되게 되는 것이다.

 

여기서 Greedy를 떠올리는 이유가 방번호를 뒤부터 넣어야한다는 점이다. 방 번호를 뒤부터 넣지 않을 경우, 최대가격과 정확히 맞아 떨어지지 않는 근사치 값을 찾을 때 가장 max한 숫자를 찾을 수 없다.

이를 위해 n부터 reversed로 for문을 탐색한다.

 

그렇다면 최대가격은 어떻게 탐색할 수 있을까?

1. 최대의 방 번호를 담는 dp배열을 선언한다.

2. p_i원 아래로는 살 수 없으므로 for문 조건을 p_i원 부터 m원 까지 순회하도록 한다.

3. 내가 떠올린 방식은 현재 가격 j로 만들 수 있는 최대 방 번호(dp[j]), 현재 숫자(i), (현재 가격 - p 가격)으로 만들 수 있는 최대 방 번호(j-p_i)에 현재 숫자(i)의 합 max 비교를 통해 탐색하는 방식이다.

 

이전에 계산된 값, 현재 숫자만 사용하는 경우, 새로 계산된 값을 비교하여 최댓값을 선택하는 방식이다.

 

이해가 잘 되지 않는다면 직접 dp 배열을 손으로 그려서 구현해보면 이해가 한층 쉬울 것이다.

입력 예시 1을 통해서 dp 테이블을 직접 그려서 점화식을 뽑아낸 과정이다.

 

# dynamic programming + Greedy Algorithm
# 현재가격 - p + 현재 방번호
# max값을 찾으면 되므로 방 뒷번호부터 탐색

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
arr = list(map(int, input().split()))
m = int(input())

dp = [-INF for _ in range(m+1)]

for i in reversed(range(n)):
    p_i = arr[i]
    for j in range(p_i, m+1):
        # dp[j-p_i] -> (현재가격 j) - p를 통해 최대가격 탐색
        dp[j] = max(dp[j], i, dp[j-p_i]*10 + i)

print(dp[m])