Python으로 푸는 백준 1793. 타일링

백준 1793. 타일링

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

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 풀이

이 문제를 이해하는데는 어렵지 않다. 다만 어떻게 풀지 막막할 뿐이다. 다이나믹 프로그래밍으로 문제를 풀기 위해서 문제를 자세히 들여다보자. 이 문제는 매번 다음 타일을 무엇을 두느냐를 결정하는 작은 문제로 나눠질 수 있다. 하나의 타일을 놓을때마다 (1) 2*1짜리를 놓을지, (2) 2*2 짜리를 놓을지, 아니면 (3)2*2를 만들기 위해서 1*2짜리를 2개를 합쳐 모양을 만들지를 고민한다.(2*1을 돌려놓으면 1*2가 된다) 다음에 놓을 수 있는 (1)(2)(3)을 이미지로 보면 아래와 같다.

다음에 놓을 수 있는 타일의 종류들

 Case2와 Case3의 모양은 서로 같다. 그 말은 즉, Case2가 놓일 수 있는 크기에는 Case3도 놓을 수 있다는 의미이다. 두 경우의 수가 크기가 같기 때문에 다음 타일을 무엇을 둘지 고민할 때 Case1, Case2, Case3를 모두 고려할 필요 없이 Case1를 놓을 수 있는 경우와 Case2를 놓는 경우를 두배해준 값을 합쳐주면 된다. 코드를 보면 더 이해하기가 쉽다. 

런타임 에러 처리 - 테스트 케이스의 수가 한정되지 않은 경우의 입력 처리

이 문제에서 가장 어려운 점은 예제를 입력받는 부분이 아니었을까 싶다. 보통 백준의 문제들을 입력하는 테스트케이스의 수가 주어지는데 이 문제의 경우에는 테스트 케이스가 몇개 인지에 대해서 입력되는 값이 없다. 1년 전에 해당 문제와 관련된 질문글에 테스트 케이스의 수가 한정되지 않은 경우에 입력을 어떻게 받는지에 대한 글이 올라와있는데 While문으로 해결할 수 있다고 적혀 있다. 그러나 더이상의 입력이 없는데도 While문으로 입력을 받기 위해 대기하고 있으면 타일의 수를 구하는 코드가 맞더라도 런타임 에러가 나게 된다. (1년 전에는 Python 버전이 달랐는지 현재는 에러가 나는듯 하다) 나는 While문으로 입력값을 받고 있었는데도 에러가 나서 질문글을 찾아보게 되었고, 무슨 에러인지는 모르겠지만 백준 서버에서 에러가 난다면 이걸 Exception 처리를 통해 핸들링해봐야 겠다고 생각했다. 그래서 Try ~ except 처리문에서 에러가 발생 시 pass하여 주도록 함으로써 문제를 해결하였다.

memo = {}
try:
    while True:
        n = int(input().strip())
        print(dp(0, n, memo))
except:
    pass

파이썬 코드

import sys
input = sys.stdin.readline
 
def dp(start, n, memo):
 
    # 마지막 위치까지 타일링 완료
    if start == n:
        return 1
 
    # 범위를 초과한 타일 처리
    if n < start:
        return 0
 
    # 저장된 값 활용하기
    if (start, n) in memo:
        return memo[(start, n)]
 
    # memoization
    memo[(start, n)] = dp(start + 1, n, memo) + 2*dp(start+2, n, memo)
    return memo[(start, n)]
 
 
if __name__ == "__main__":
    memo = {}
    try:
        while True:
            n = int(input().strip())
            print(dp(0, n, memo))
    except:
        pass