벽돌이라고 하는 숫자 목록과 너비와 높이의 다른 두 값 목록이 있다고 가정합니다. 벽돌[i]의 각 요소는 길이가 벽돌[i] 단위이고 너비가 1단위인 벽돌을 나타냅니다. 주어진 너비와 높이로 벽돌의 전체 레이아웃을 얻을 수 있도록 벽돌을 쌓는 방법의 수를 찾아야 합니다. 벽돌을 재사용할 수 있지만 수평으로만 놓을 수 있습니다.
따라서 입력이 벽돌 =[2, 1] 너비 =3 높이 =2와 같으면 출력은 −
이기 때문에 9가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- w :=너비와 같은 크기의 목록으로 첫 번째 위치에 1을 삽입하고 나머지는 0
- 0에서 너비까지 범위에 있는 i에 대해
- w[i]가 0이 아니면
- 벽돌의 각 x에 대해 다음을 수행합니다.
- i + x <=너비이면
- w[i + x] :=w[i + x] + w[i]
- i + x <=너비이면
- 벽돌의 각 x에 대해 다음을 수행합니다.
- w[i]가 0이 아니면
- 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