1082 - 방 번호

n = int(input())

arr = list(map(int, input().split()))

m = int(input())

dp = [0] * 51

for idx, i in enumerate(arr):
    if idx:
        dp[i] = max(dp[i], idx)

answer = 0
for money in range(m + 1):
    for idx, cost in enumerate(arr):
        if money +cost <= m:

            dp[money + cost] = max(dp[money + cost] , (dp[money]* 10) + idx)
            answer = max(answer ,dp[money + cost])
print(answer)

간단한 다이나믹 프로그래밍 문제

dp[현재 가지고 있는 돈으로 가장 큰 방 번호] 로 정의 하였고

풀이는

loop를 두번 돌면서
for 현재 가지고 있는 돈 ~ m
for 방번호, 방 번호의 값 ~ Pn-1
dp[현재 가지고 있는 돈 + 방 번호의 값] = max(dp[현재 가지고 있는 돈 ] * 10 + 방 번호 , dp[현재 가지고 있는 돈 + 방 번호의 값] )
으로 풀었다.

루프를 두 번 돌기에 시간 복잡도는 O(N^2)이다.