[백준][Python] 18427 함께 블록 쌓기

박스 순회하며 누적합. 자주나오는 유형이다. 중요한건 누적합은 뒤에서부터 쌓아줘야 중복이 안생긴다는것.

때문에 H부터 1까지 순회해주며 더해줬다.

 

import sys
input = sys.stdin.readline

N, M, H = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(N) ]
dp = [0]*(H+1)

for box in boxes:
    for idx in range(H,0,-1):
        if not dp[idx]: continue
        for num in box:
            if idx + num > H: continue
            dp[idx+num] += dp[idx]
    for num in box:
        dp[num] += 1
print(dp[H]%10007)