백준 11726번: 2xn 타일링

백준 11726번: 2xn 타일링

아이디어

n번째까지 타일로 채우는 방법의 수는 n-2번째까지 타일로 채우는 방법의 수 + n-1번째까지 타일로 채우는 방법의 수이다. 그림을 통해 알아보자.

n-1번까지 채워진 상태에 2x1 타일 한개를 붙이는 경우와 n-2번까지 채워진 상태에 1x2 타일 두개를 붙이는 경우 두가지가 존재한다. 이때 n-2번까지 채워진 상태에 2x1 타일 두개를 붙이는 경우를 세지 않는 이유는 n-1번까지 채워진 상태에 2x1 타일 한개를 붙이는 경우에 포함되기 때문이다.

코드

N = int(input())
if N > 2:
    dp = [1, 2] + [0]*(N - 2)
    for i in range(2, N):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[-1] % 10007)
else:
    print(N)

여담

이와 비슷한 문제로 백준 11727번: 2xn 타일링 2가 있다. 2x2 타일이 하나 추가됐는데 이 때 n-2까지 채워진 상태에 1x2 타일 두개를 붙이는 경우와 2x2 타일 한개를 붙이는 경우 모두 합해주면 된다. 코드는 다음과 같다.

N = int(input())
if N > 2:
    dp = [1, 3] + [0]*(N - 2)
    for i in range(2, N):
        dp[i] = dp[i - 1] + dp[i - 2]*2
    print(dp[-1] % 10007)
else:
    dp = [1, 3]
    print(dp[N - 1])