[Python] 백준 1082: 방 번호

https://www.acmicpc.net/problem/1082

1082번: 방 번호

 

1. 가장 큰 방 번호를 출력하므로 뒤에서부터 dp를 시작한다.

2. 현재 값, 현재 인덱스 값(현재 dp가 무한일 수도 있기 때문), 전의 값 * 10 + 현재 값 중 가장 큰 값을 넣는다.

INF = 5001
n = int(input())
room = list(map(int, input().split()))
m = int(input())
dp = [-INF for _ in range(m+1)]
for i in range(n-1, -1, -1):
    x = room[i]
    for j in range(x, m+1):
        dp[j] = max(dp[j-x]*10+i, i, dp[j])

print(dp[m])