[백준 18427번] 파이썬 - 함께 블록 쌓기

백준 18427 - 함께 블록 쌓기

시간 제한 1초, 메모리 제한 256MB

# 조건

• 1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.

단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다.

1번부터 N번까지의 학생들이 가지고 있는 블록들에 대한 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.

예를 들어 N=3, M=3, H=5일 때, 각 학생마다 가지고 있는 블록들의 높이가 다음과 같다고 가정하자.

• 1번 학생: 2, 3, 5
• 2번 학생: 3, 5
• 3번 학생: 1, 2, 3

이 때, 탑의 높이가 정확히 5가 되도록 블록을 쌓는 경우로는 다음의 6가지가 존재한다. (블록을 사용하지 않는 경우는 X로 표시하였다.)

# 접근 방법

• 냅색 알고리즘과 같다.
• 현재 블록을 쌓았을 때와 그렇지 않은 경우만 잘 구분해주면 된다.
• 우선 res H+1의 크기만큼 N개를 가지 2차원 배열 res를 생성해주고, 각 행의 0번 인덱스 => 아무것도 쌓지 않은 경우를 1로 초기화 해준다.
• 이후, 모든 사람을 순회하며 아래 로직을 수행한다.
  • 이전 학생이 (구하는 높이-사용하려는 블럭 높이)를 쌓을 때 가능한 경우의 수를 갖고 와서 더해준다.

import sys
input = sys.stdin.readline
from copy import deepcopy

N, M, H = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(N)]

res = [[1] + [0] * (H) for _ in range(N+1)]

for i in range(1, N+1):
    res[i] = deepcopy(res[i-1])
    for j in info[i-1]:
        for k in range(j, H+1):
            res[i][k] += res[i-1][k-j]
print(res[N][H] % 10007)