백준 18427 함께 블록 쌓기

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

18427번: 함께 블록 쌓기

문제 접근법 : 배낭문제이지만

dfs+재귀로 풀려고했는데

메모리는 충분히 가능하지만 메모이제이션을 사용한다해도

최악의경우 50^10 이니 너무 커서 시간초과가 나더군요

 

buttom up방식을 이용해서 경우의수로 구해야합니다.

 

소스코드 : 

import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
n,m,h = map(int,input().rstrip().split())
l = [list(map(int,input().rstrip().rsplit())) for i in range(n)]
dp =[[0 for i in range(h+1)] for j in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    dp[i] = dp[i-1][:]
    for j in l[i-1]:
        for k in range(j,h+1):
            dp[i][k] += dp[i-1][k-j]
            dp[i][k]%=10007
print(dp[n][k])

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