백준 1793번 파이썬 코드 답

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

문제풀이

 

딱 보면 작은 문제가 반복되어서 큰 문제를 풀 수 있는 전형적인 다이나믹 프로그래밍 문제라는 것을 알 수 있다. 이런 문제라는 것을 눈치 챘다면, 점화식이 어떻게 될지를 생각해봐야 한다. 점화식을 생각하는 방법은 생각보다 간단했다. 경우를 나누고, 그 경우를 메모리제이션을 통해서 풀 수 있게 생각을 하면 된다.

나 같은 경우는 다음과 같은 경우로 나누었다.
An : 2*1 (세로)를 마지막에 하나 붙여서 만들 수 있는 경우의 수
Bn : 2*1 (가로)를 마지막에 두개 붙여서 만들 수 있는 경우의 수 (2*1 가로는 2개씩 붙여야 칸이 찬다)
Cn : 2*2 를 마지막에 1개 붙여서 만들 수 있는 경우의 수(2*2는 1개만 붙이면 된다)

그렇다면 각 A,B,C 사이에는 다음과 같은 점화식이 성립하는 것을 알게 된다.
An = An-1 + Bn-1 + Cn-1 
Bn = An-2 + Bn-2 + Cn-2
Cn = An-2 + Bn-2 + Cn-2 

당연하게도 세로 한 줄을 붙이는 것은 한 칸만 공간이 있으면 된다. 예를 들어서 4번째까지 다 채웠다고 가정했을 때, 5번째를 채우려면 세로 한 줄을 붙이는 건 어떤 경우의 수든 가능하다. 따라서 An-1 + Bn-1 + Cn-1이 된다. Bn과 Cn은 유사한 논리인데 2칸을 채우려면, 2칸이 비워져 있어야 한다. 따라서 Bn,Cn = An-2 + Bn-2 + Cn-2 이다.

점화식 자체는 굉장히 간단했는데, 이 문제를 풀면서 알게 된 점은 하나가 있다. 바로 n = 0일 때의 값이다. n=0일 때 값은 1이어야 하는데, 그 이유는 아무것도 하지 않는 것도 한 방법이기 때문이라고 한다. 예를 들어 사물 0개를 일렬로 나열하는 방법의 수는 0!인데, 0!=1이다. 즉, 아무것도 하지 않는 것도 한 가지 방법이라고 볼 수 있기 때문에 그렇게 본다고 한다. 요거는 꽤 유용한 생각인 것 같다. 여튼, 코드는 아래와 같다.

import sys
a = [ 0 for _ in range(251)]
b = [ 0 for _ in range(251)]
c = [ 0 for _ in range(251)]

a[0] = 1
a[1] = 1
a[2] = 1
b[1] = 0
b[2] = 1
c[1] = 0
c[2] = 1

for i in range(3,251) :
    a[i] = a[i-1] + b[i-1] + c[i-1]
    b[i] = a[i-2] + b[i-2] + c[i-2]
    c[i] = a[i-2] + b[i-2] + c[i-2]

while 1 :
    try :
        n = int(sys.stdin.readline().rstrip())
    except :
        exit()
    print(a[n] + b[n] + c[n])