(Python/🥇3)백준알고리즘 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원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다

 

 

풀이:

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
prices = list(map(int, sys.stdin.readline().rstrip().split()))

# 가진 돈
money = int(input())

# n 원으로 만들 수 있는 가장 큰 숫자
# dp[n] n원 만드는데 가장 큰 숫자
dp = [0 for _ in range(money + 1)]
for i in range(1, money + 1):
    for number, price in enumerate(prices):
        # 현재내가 가진 금액으로 숫자를 살 수 있을경우
        if i >= price:
            dp[i] = max(dp[i], int(str(dp[i - price]) + str(number)))
print(dp[money])

 

가방 문제 랑 비슷하다

 

각 숫자에는 가격이 있다.

 

내가 가진 돈으로 만들 수 있는 가장 큰 수를 만든다.

 

점화식은, 현재 돈으로 만들수 있는 최댓값과, 현재 돈 에서 살 수 있는 다른 숫자를 더 했을때 더 큰 값을 비교한다.

 

숫자는 문자열 형식이라 자릿수가 클 수록 크다.