숫자로 이루어진 리스트 bricks와 두 개의 값 width(너비), height(높이)가 주어졌다고 가정해 보겠습니다. bricks[i]의 각 원소는 길이가 bricks[i] 단위이고 폭이 1단위인 벽돌 하나를 나타냅니다. 목표는 주어진 너비와 높이에 맞게 벽돌로 공간을 빈틈없이 채우는 배치 방법이 총 몇 가지인지 구하는 것입니다. 이때 벽돌은 자유롭게 재사용할 수 있지만, 반드시 가로 방향으로만 놓아야 한다는 조건이 있습니다.
예를 들어 bricks = [2, 1], width = 3, height = 2가 입력으로 주어지면 정답은 9가 됩니다. 너비 3인 한 줄을 채우는 방법은 [1, 1, 1], [1, 2], [2, 1]의 세 가지이고, 두 줄은 서로 독립적이므로 3 × 3 = 9가 되기 때문입니다.
동적 계획법(DP) 접근 방식
이 문제는 동적 계획법을 이용해 효율적으로 해결할 수 있습니다. 핵심은 w[i]를 '너비 i만큼을 벽돌로 채우는 방법의 수'로 정의하는 것입니다. 구체적인 절차는 다음과 같습니다.
- 초기화: 크기가 width + 1인 리스트 w를 만들고, 첫 번째 위치(w[0])에는 1을, 나머지는 모두 0으로 설정합니다. w[0] = 1은 '아무것도 놓지 않는 한 가지 방법'을 의미하는 기저 사례입니다.
- 점화식 적용: i를 0부터 width − 1까지 순회하면서, w[i]가 0이 아니면(즉 해당 지점까지 도달 가능한 경우가 있으면) bricks의 각 벽돌 길이 x에 대해 i + x ≤ width를 만족할 때 w[i + x] += w[i]로 값을 누적합니다.
- 결합: 마지막에 w[width] ** height를 반환합니다. 각 행은 서로 독립적으로 채워지므로, 한 행을 채우는 방법의 수를 높이만큼 거듭제곱하면 전체 배치 방법의 수가 됩니다.
예제 실행 흐름 살펴보기
bricks = [2, 1], width = 3일 때 DP 배열의 변화는 다음과 같습니다.
- 초기 상태: w = [1, 0, 0, 0]
- i = 0: w[2] += 1, w[1] += 1 → w = [1, 1, 1, 0]
- i = 1: w[3] += 1, w[2] += 1 → w = [1, 1, 2, 1]
- i = 2: w[3] += 2 → w = [1, 1, 2, 3]
따라서 한 줄을 채우는 방법은 w[3] = 3가지이며, 높이가 2이므로 최종 답은 3² = 9입니다.
Python 구현 코드
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
시간 복잡도
벽돌 종류의 수를 k라고 하면 DP 배열을 채우는 데 O(width × k)의 시간이 걸리며, 마지막 거듭제곱 연산은 매우 빠르게 처리됩니다. 따라서 너비나 벽돌 종류가 늘어나더라도 효율적으로 동작하는 알고리즘입니다.