[🥇3 / 백준 1082 / 파이썬] 방 번호

 

 

 

 

 

1082번: 방 번호

 

문제

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 P_i이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P₀ = 6, P₁ = 7, P₂ = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

 

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., P_N-1이 주어진다. 마지막 줄에는 M이 주어진다.

 

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

 

제한

• 1 ≤ N ≤ 10
• 1 ≤ P_i ≤ 50
• 1 ≤ M ≤ 50
• N, P_i, M은 정수

 

예제 입력 1 3 6 7 8 21	예제 출력 1 210
예제 입력 2 3 5 23 24 30	예제 출력 2 20
예제 입력 3 4 1 5 3 2 1	예제 출력 3 0
예제 입력 4 10 1 1 1 1 1 1 1 1 1 1 50	예제 출력 4 99999999999999999999999999999999999999999999999999

 

 

풀이

 

가능한 한 높은 번호를 앞에 우선시키는 것이 더 큰 방 번호를 만들 수 있으므로 높은 번호부터 낮은 번호로 순회하며 만들 수 있는 가장 큰 방 번호를 찾아야 한다.

 

import sys
input = sys.stdin.readline

n = int(input())
costs = list(map(int, input().split()))
m = int(input())
dp = [-1]*(m+1)
# 숫자를 내림차순으로 순회
for num in range(n-1, -1, -1):
    # 현재 숫자의 cost 부터 최대 가격까지 순회
    for cost in range(costs[num], m+1):
        dp[cost] = max(num, dp[cost], dp[cost-costs[num]]*10 + num)
print(dp[-1])