블록 개수 구하기

문제 설명

2 X 1과 2 X 2 크기의 블록을 2 X n 크기의 직사각형 모양 틀에 넣으려고 한다. 가능한 경우의 수를 구하세요.

단, 블록은 충분한 개수가 있다고 가정한다.

입력

직사각형 모양 틀의 가로 길이 n을 입력

출력

경우의 수를 출력한다.

입출력 예

n	result
6	43
8	171

풀이

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 3

    arr = [1, 3]

    for i in range(2, n):
        arr.append(arr[i - 1] + arr[i - 2] * 2)

    return arr[-1]

해결 과정

Bottom Up 방식으로 해결할 수 있는 문제다. 일단 이 문제를 해결하기 위한 공식은 다음과 같다.

solution(n) = solution(n - 1) + solution(n - 2) * 2

왜 이렇게 되는지는 2 * 5(즉, n = 5)일 때를 예로 들어보자.

solution(5)는 2 X 4의 경우에 2 X 1 블록이 추가되는 것이다. 이 경우는 방법이 결국 한 가지 밖에 없으므로 2 X 4밖에 없다.

2 X 3을 2 X 5에 대입하면 2 X 2가 남게 되는데, 이때, 2 X 1을 세로 방향으로 세워서 넣는 것은 불가능하다.

왜냐하면 이미 2 X 4의 경우에서 2 X 1 두 개가 세로인 경우를 구했기 때문이다.

고로 그를 제외한 2 X 1 두 개를 가로 방향으로 눕히는 것과 2 X 2 블록을 사용하는 경우를 해서 2개의 경우가 추가된다.

따라서, 2 X 3의 값에 2를 곱하는 것이다.