백준(BOJ) 1082 방 번호(Python)

 

문제 내용

 

DP 문제.

현재 가지고 있는 금액을 i로 하고, 최대 방 번호를 dp[i]로 하는 배열을 설정한다.

초기 설정은 모두 0이다. 이는 숫자의 가격을 고려하지 않고 만들어질 수 있는 최소 방 번호가 0이기 때문이다.

같은 숫자 구성을 한 경우 내림차순으로 정렬된 경우가 가장 번호가 큰 경우이므로, 9부터 0까지 번호를 채워나간다.

숫자를 살 수 있으면 사기 전의 금액에서 최대 번호의 맨 뒤에 현재 구매한 숫자를 추가하는 방식으로 dp를 갱신한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
P=list(map(int,input().split()))
m=int(input())
dp=[0 for i in range(m+1)]
for i in range(n-1,-1,-1):
    for j in range(P[i],m+1):
        dp[j]=max(dp[j],dp[j-P[i]]*10+i)
print(dp[m])

 

처음에는 백트래킹으로 해보려고 했는데, 구현을 못해서 도중에 포기했다.

더 노력해야겠다.