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

문제 보러 가기

DP로 풀었다 !!

특정 숫자의 가격은 딕셔너리에 저장해뒀다. (그런데 생각해보니 어차피 0~ N-1 순서니까 그냥 리스트에 가격을 저장했어도 될 것 같다.)

dp 리스트의 인덱스는 돈, 값은 그 돈으로 살 수 있는 제일 큰 방 번호를 의미한다. 각 값은 '-'으로 초기화해뒀다. 처음에는 0으로 했는데, 그러면 숫자 0을 살 수 있다는 뜻인지, 아무것도 못 산다(or 안 샀다)는 뜻인지 구분이 안가서 '-'으로 했다.  

그 후에 dp 세팅을 했다. 각 숫자를 하나 사는 경우를 dp에 넣어줬다. dp[그 숫자의 가격] = 그 숫자 로 해줬다.

그 다음에는 본격적인 DP!

숫자 가격이 젤 작은 것 X 2부터 M까지 쭉 ~ 보는데, 그 지점에서 각 숫자 가격을 뺀 위치의 값과 비교했다. 다시 말하면, 그 지점으로 어떻게 올 수 있는지 봐주면서, 여러 방법으로 올 수 있으면 젤 큰 값을 저장하는 것이다. 예를 들어서, 그 지점으로 오기 전에 숫자 1을 샀다면 dp[그 지점]은 dp[그 지점]과 dp[1의 가격을 뺀 지점]X10 + 1 값 중에 큰 값으로 하면 된다.

주의할 점💫

• 지문에는 'M원을 모두 사용해야 한다.'라고 되어 있는데, 예제 3을 보면 그게 아니다...ㅠㅠ 게시판에 관련된 글이 있는데, 곧 반영되겠지..?!!
• 각 지점에서 각 숫자 가격을 뺐을 때 dp 리스트의 값을 볼 때 음수인지 체크해야 한다. 즉, (i-now_price)>=0 조건을 체크해야 한다. 안 했더니 마이너스가 되어버려서, 이상한 인덱스의 값을 가져오는 경우가 있었다ㅠ

코드 👩‍💻

import sys

input = sys.stdin.readline

N = int(input())
price = {}
tmp = list(map(int, input().split()))
for i in range(N):
    price[i] = tmp[i]

M = int(input())
dp = ['-'] * (51)  # 그 돈으로 살 수 있는 제일 큰 방 번호

# 초기 세팅
for i in range(N):
    now_price = price[i]
    dp[now_price] = i

for i in range(min(price.values()) * 2, M + 1):
    for j in price.keys():
        now_price = price[j]
        if dp[i - now_price] != '-' and (i - now_price) >= 0:
            if dp[i] == '-':
                dp[i] = 0
            dp[i] = max(dp[i], dp[i - now_price] * 10 + j)

new_dp = []
for i in range(1, M+1):
    if dp[i] == '-':
        pass
    else:
        new_dp.append(dp[i])
print(max(new_dp))