[백준] 18427 함께 블록 쌓기

문제

• 1~N번까지의 학생이 최대 M개의 서로 다른 높이의 블록들을 갖고 있다.
• 1번부터 N번까지 학생들이 차례로 바닥에서부터 블록을 쌓으려고 한다.
• 한 학생당 최대 1개의 블록만 사용할 수 있을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수 구하기
• 경우의 수를 10,007로 나눈 나머지 구하기
  
  
• 1 <= N <= 50
  1 <= M <= 10
  1 <= H <= 1000

 

풀이 1 (실패)

• 각 학생별로 (아무것도 쌓지 않는 것 + 각 블럭 쌓았을 때) 만들 수 있는 높이를 구한다.

메모리 초과

from collections import deque

N, M, H = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)] # 전체 블럭들 저장

# dp[i] : i번째 학생이 블럭을 쌓았을 때 만들 수 있는 높이

dp = [[] for _ in range(N)]
dp[0] = [0] + blocks[0]     # 1번째 학생 블록 쌓는 경우의 수

for i in range(1, N) :
    while dp[i-1] :
        h = dp[i-1].pop()   # 현재 높이 
        dp[i].append(h)     # i번째 학생이 블럭 쌓는 경우의 수
        dp[i].extend([h+b for b in blocks[i] if h+b <= H])

print(dp[N-1].count(H) % 10007)

 

풀이 2

• 이전 학생의 높이는 한 번 참고 후 더이상 필요하지 않으므로 바로 이전 학생의 높이만 저장하도록 한다.
• 또한, 딕셔너리를 통해 높이 별로 경우의 수를 저장해 메모리 사용을 줄인다.

 

from collections import defaultdict

N, M, H = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)] # 전체 블럭들 저장

# dp : n번째 학생이 블럭을 쌓았을 때 만들 수 있는 높이
dp = {b : 1 for b in [0] + blocks[0]} # 1번째 학생 블록 쌓는 경우의 수  

for i in range(1, N) :
    nxt = defaultdict(int)
    for k, v in dp.items() :
        # i번째 학생이 블럭 쌓는 경우의 수
        nxt[k] += v
        for b in blocks[i] :
            if b+k <= H :
                nxt[b+k] += v
    dp = nxt

print(dp[H]%10007) if H in dp else print(0)

 

 

 

References

• 백준 DP