[BOJ 1082🥇3] 방 번호 (Python)

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

1082번: 방 번호

문제

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

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

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

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

제한

• 1 ≤ N ≤ 10
• 1 ≤ Pi ≤ 50
• 1 ≤ M ≤ 50
• N, Pi, M은 정수

예제 입력 1

3
6 7 8
21

예제 출력 1

210

예제 입력 2

3
5 23 24
30

예제 출력 2

20

예제 입력 3

4
1 5 3 2
1

예제 출력 3

0

예제 입력 4

10
1 1 1 1 1 1 1 1 1 1
50

예제 출력 4

99999999999999999999999999999999999999999999999999

 

⭕ CODE

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

d = [-10000 for _ in range(m+1)]
# 방 번호 높은 순 조회
for i in range(n-1,-1,-1):
    # 방 가격
    x = arr[i]
    # x원 밑으로는 살 수 없으므로 x원부터 m원까지 조사
    for j in range(x,m+1):
        # d[j] : 현재 방 번호
        # i : 현재 인덱스
        # d[j-x]*10+i :현재 가격에서 x원 만큼 뺀거에 x원만큼 살 수 있는거
        d[j] = max(d[j],i,d[j-x]*10+i)

print(d[m])

✏️ Comment

문제를 보고 높은 방 번호부터 조사해야한다는 생각은 가지고 있었지만 쉽게 점화식을 세울 수 없었다.
이번 문제는 다른 사람들의 코드를 보고 풀었다.

처음에는 방 번호와 가격을 가지고 2차원 테이블 dp를 만들었는데 그럴 필요가 없더라

 

• dp 너무 어렵다.