(Python/파이썬) - 백준(BOJ) 1082번 : 방 번호

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

1082번: 방 번호

---

• 문제 : 

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

 

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

 

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. M원을 모두 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

 

 

 

---

• 풀이 :

DP 문제였습니다.

 

풀이입니다.

 

1. 방 번호가 높은 순서대로 가져올 수 있는 최댓값을 갖고와야 하므로 방 번호를 n-1부터 0까지 내림차순으로 실행

 

2. 해당 가격으로 살 수 있는 최대의 방 번호를 담아두기 위해 dp 배열을 선언한다.

 

3. 가격에 대한 dp 배열이므로 가격인 p 부터 최대 가격인 M까지 ( p 이하는 어짜피 p를 살 수 없으므로 고려하지 않는다.) 순회하며 (현재 방 번호, 현재 인덱스, 현재 가격 - p 에 p로 살 수 있는 방 번호를 붙인 값) 중 max로 갱신해주면 된다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

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