알고리즘/BOJ

[Python] 백준 1082: 방 번호

PIAI 2021. 9. 25. 17:55

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

 

1082번: 방 번호

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

www.acmicpc.net

 

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])