풀이

1. 가지고 있는 예산 기준 가장 높은 방 번호를 구해야한다.
2. 방 번호가 높은 순서부터 차례대로 예산에 입력해보자.

DP[15]=max(DP[15],DP[15-7]*10+2) 로 비교하게 된다.

방 번호가 높은 순서부터 차례대로 고려하는 이유는, 23,32 모두 같은 예산이 드는데, 32가 더 큰 수이기 때문에, 번호가 높은 순서부터 예산 테이블에 입력하는 것이다.

재귀식을 DP[j]=max(DP[j],DP[j-price]*10+number(price에 해당하는 number),number)로 세울 수 있다.

import sys
input=sys.stdin.readline
n=int(input())
p=list(map(int,input().split()))
m=int(input())
DP=[-sys.maxsize]*(m+1)
for i in range(n-1,-1,-1):
    price=p[i] # p[i] is cost , i is number
    for j in range(price,m+1):
        DP[j]=max(DP[j],DP[j-price]*10+i,i)

print(DP[m])