백준 14728 벼락치기

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

14728번: 벼락치기

 

문제 접근법:

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

 

내가 가지고있는 시간으로 풀수있는 문제는

풀거나 혹은 안풀고 다른문제로 넘어가거나 하여 모든 경우의수를 dfs로 풀면됩니다.

 

그리고 메모이제이션을 이용해서 가지치기를 하면

쉽게 풀수있는 문제입니다.

파이썬으로 푼 문제입니다.

소스코드 :

 

import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
n,t = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
dp = [[-1 for j in range(t+1)] for i in range(n)]

def dfs(cur=0,sum=0):
    global l,dp,t
    if cur>=len(l):return 0
    if dp[cur][sum]!=-1: return dp[cur][sum]
    if sum+l[cur][0]<=t:
        dp[cur][sum]=max(dp[cur][sum],dfs(cur+1,sum+l[cur][0])+l[cur][1])
    dp[cur][sum]=max(dp[cur][sum],dfs(cur+1,sum))
    return dp[cur][sum]

print(dfs())

 

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