[ProblemSolving] 백준 - 11727 2*n타일링2(dp)

문제 링크

문제 설명

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

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

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력1

2

예제 출력1

3

예제 입력2

8

예제 출력2

171

예제 입력3

12

예제 출력3

2731

나의 풀이

몇가지 dp 문제를 풀면서 느낀 점은 맨 뒤에서 규칙을 찾으면 점화식을 도출하기가 쉬워지는 것 같다.

이 문제도 마찬가지로 뒤에서 생각한다.

가로의 길이가 i개인 타일일때, i-1까지 이미 채워져있다면 2x1 덮개를 채울 수 있다.

i-2까지 이미 채워져 있다면, 1x2 2개, 2x2 1개 덮개를 채우는 2가지의 경우가 있다. 여기서 2x1 덮개는 고려하지 않는다. 위에서 고려되었기 때문이다.

점화식으로 표현하면 dp[i] = dp[i-1] + dp[i-2]*2

주의할 점

쉽게 쉽게 풀었지만 함정이 있었다.

코드에서 보면, n=1을 입력받으면,

dp[2]=3 초기화 해준 부분에서 컴파일 에러가 발생하니까,

n=1일때 예외 처리를 해줘야 한다.

코드

n = int(input())

dp = [0]*(n+1)

if n < 2:
    print(1)
    
else:
    dp[1] = 1
    dp[2] = 3
    for i in range(3, n+1):
        dp[i] = dp[i-1] + 2*dp[i-2]
    print(dp[n]%10007)