백준 1082 - 방 번호

문제 링크 : https://www.acmicpc.net/problem/1082

 

문제

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

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

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

입력

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

출력

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

풀이 과정

냅색 이론을 응용하여 특정 숫자를 구매했을 때 만들 수 있는 가장 큰 수를 DP 배열에 저장한다.

# 1082. 방 번호 ( GOLD 3 )

import sys
input = sys.stdin.readline

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


# 가장 큰 번호 하나 사고 저렴한 숫자 왕창 사기? -> 210 반례때문에 불가능
# dp[i][j] : i원으로 마지막에 j를 구매했을 때 가장 큰 숫자

dp = [[-1 for _ in range(n)] for _ in range(m+1)] 
for i in range(1, m+1):
  for j in range(n):
    if p[j] > i: continue
    if dp[i][j] == -1:
      dp[i][j] = j
    for k in range(n):
      if dp[i-p[j]][k] != -1:
        dp[i][j] = max(dp[i][j], int(''.join(map(str, sorted(list(map(int, list(str(dp[i-p[j]][k])))) + [j], reverse=True)))))
  
print(max(dp[m]))