수평 벽돌 패턴의 수를 세는 프로그램은 Python에서 벽돌 세트로 만들 수 있습니다.

벽돌이라고 하는 숫자 목록과 너비와 높이의 다른 두 값 목록이 있다고 가정합니다. 벽돌[i]의 각 요소는 길이가 벽돌[i] 단위이고 너비가 1단위인 벽돌을 나타냅니다. 주어진 너비와 높이로 벽돌의 전체 레이아웃을 얻을 수 있도록 벽돌을 쌓는 방법의 수를 찾아야 합니다. 벽돌을 재사용할 수 있지만 수평으로만 놓을 수 있습니다.

따라서 입력이 벽돌 =[2, 1] 너비 =3 높이 =2와 같으면 출력은 −

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• w :=너비와 같은 크기의 목록으로 첫 번째 위치에 1을 삽입하고 나머지는 0
• 0에서 너비까지 범위에 있는 i에 대해
  • w[i]가 0이 아니면
    • 벽돌의 각 x에 대해 다음을 수행합니다.
      • i + x <=너비이면
        • w[i + x] :=w[i + x] + w[i]
• w[너비]^높이를 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(bricks, width, height):
   w = [1] + [0] * width
   for i in range(width):
      if w[i]:
         for x in bricks:
            if i + x <= width:
               w[i + x] += w[i]
   return w[width] ** height

bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))

입력

[2, 1], 3, 2

출력

9