백준 1106 - 호텔

10 Sep 2021 | dp

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

dp문제를 처음 풀어봤는데 점화식을 세우는 것이 막막했다.

문제의 핵심은 dp[비용] = 사람 수 로 정의하고,

dp[현재 비용] + 추가 사람 수 > dp[현재 비용 + 추가 비용] 인 경우에

dp[현재 비용 + 추가 비용]에 추가된 사람 만큼 update를 해주는 점화식을 정의해서 문제를 풀면 된다.

dp 문제 푸는 경험을 더 늘려야 겠다.

import sys

sys.setrecursionlimit(10000)

def solution(c, num, infos):
    if costs[num] >= c:
        answers.append(num)
        return
    
    for value, customer in infos:
        if costs[num] + customer > costs[num+value]:
            costs[num+value] = costs[num] + customer #update
            solution(c, num+value, infos)
            


if __name__ == '__main__':
    c, n = map(int,input().split())# customer, num of city
    infos =  [list(map(int, input().strip().split())) for _ in range(n)]
    costs = [0] * 100 * 1000 + [0] # dp[비용] = 사람수
    answers = []
    solution(c, 0, infos)
    print(min(answers))

Related Posts

Comments