백준 1106 호텔

문제 URL : https://www.acmicpc.net/problem/1106

1106번: 호텔

 

문제 접근법 : 

 

dfs + 메모이제이션문제입니다.

 

홍보를 할땐하더라도 비용이드는 최소가 되도록 전수 조사로 재귀를 짜시면됩니다.

 

그후 메모이제이션으로 가지치기를 하시면 쉽게 해결할수있는 문제입니다.

파이썬 으로 쉽게할수있는 문제라 파이썬으로 풀었는데

재귀깊이가 n= 20이라 100만까지 갈수있으니 재귀 깊이를 늘려줘야한다는거 잊지마시길

 

소스코드 :

import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
c,n = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
dp = [100000000 for i in range(10000)]

def dfs(l,dp,people):
    if people<= 0:return 0
    if dp[people]!=100000000:return dp[people]
    for i in range(len(l)):
        dp[people]= min(dfs(l,dp,people-l[i][1])+l[i][0],dp[people])
    return dp[people]
print(dfs(l,dp,c))

궁금한점 혹은 모르는점  어떤질문이든 댓글은 언제나 환영입니다.