[Python/파이썬] 백준 1082번 방 번호

1082번: 방 번호

 

문제

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

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

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 10
• 1 ≤ $P_i$ ≤ 50
• 1 ≤ M ≤ 50
• N, $P_i$, M은 정수

 

코드

처음 시도한 풀이(DFS) => 틀렸음

n = int(input())
p = list(map(int, input().split()))
m = int(input())
ans = '0'

def dfs(room_number, remain_money):
    global ans
    if len(room_number) > 50:
        return
    if remain_money <= 0:
        return
    for i in range(n-1, -1, -1):
        if remain_money >= p[i]:
            if int(ans) < int(room_number+str(i)):
                ans = room_number+str(i)
            dfs(room_number+str(i), remain_money-p[i])

dfs('', m)
print(ans)

예제 3과 같은 경우에 문제가 발생한다.

어떻게 처리할지 도저히 모르겠어서 아래에서 알고리즘 분류를 봤더니 다이나믹 프로그래밍, 그리디 알고리즘으로 분류되어있길래 DP로 아예 방향을 바꿔서 다시 풀었다.

 

맞은 코드(Dynamic Programming)

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

dp = ['0'] * (m+1)    # 금액별 가능한 최대 방 번호

for money in range(1, m+1):  # 금액
    for num in range(n):
        if money-p[num] >= 0:
            dp[money] = str(max(int(dp[money-p[num]])*10+num, int(dp[money])))

print(dp[m])

dp 배열에는 인덱스를 금액이라고 보고 배열 값에는 금액별로 가능한 최대 방 번호를 저장한다.

처음에는 배열에 저장되는 값들을 정수로 하고 초기값을 0으로 모두 넣어주고 했는데 이 경우 끝이 0으로 끝나는 숫자가 최대 방 번호일 때 문제가 발생하여 문자열로 처리하였다.