[BOJ] 백준 1082번: 방 번호

1일 1PS 16일차!

📚 문제

---

골드 3

• DP 를 사용한다.
• 가장 큰 숫자부터 가져온다.

💡 포인트

---

1. p부터 M 가격까지 순회하면서 max(현재 방 번호, 현재 인덱스, 현재 가격 - p 에서 p로 살 수 있는 방 번호를 붙인 값) 로 갱신한다.

💻 코드

---

N = int(input())
P = list(map(int,input().split()))
M = int(input())
dp = [-float("inf") for _ in range(M+1)]
for i in range(N-1,-1,-1):
    p = P[i]
    for j in range(p, M+1):
        dp[j] = max(dp[j], i, dp[j-p]*10 + i)
print(dp[M])