[백준] 11727 2xn 타일링 2 (파이썬 Python)

 

https://www.acmicpc.net/problem/11727

문제 설명

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

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

---

풀이 과정 

• 나의 풀이 

①  이 문제에서 직관적으로 파악한 것은 '11726문제와 같이 DP문제이고, 결과 혹은 과정에 의한 규칙이 분명 존재하겠구나'이다. 

② 아이디어 열기 

 우선 n의 값에 따른 문제의 과정과 결과에 대해 알아보자. 

 n = 1 ; 1 

 n = 2 ; 3

 n = 3 ; 5

 n = 4 ; 11

 n = 5 ; 21 

 n = 6 ; 43 

 ...

 결과에 의해서는 한눈에 규칙이 안보인다.

 그러므로 과정에 집중해보자..!

  n = 4인경우 경우의 수는 n = 3인 경우에서 2x1 타일을 붙인 경우와 n = 2인 경우에서 2x2 타일을 붙인 경우와 1x2 타일 2개를 붙인 경우의 합이다. 

  이를 일반화하면 다음과 같다.

  <2xn 크기의 직사각형을 채우는 방법의 수>

(1) 2x(n-1)만큼 타일링하는 방법의 수에다가 2x1타일 붙이는 경우

(2) 2x(n-2)만큼 타일링하는 방법의 수에다가 2x2타일 붙이는 경우

(3) 2x(n-2)만큼 타일링하는 방법의 수에다가 1x2타일 2개를 붙이는 경우

  이를 점화식의 형태로 나타내면 다음과 같다.

 f(n) = f(n-1) + 2xf(n-2) (n>=3) , f(1) = 1 , f(2) = 3 

  마지막으로 실제 코드로 구현해보면 다음과 같다.

# 11727
n = int(input())

if n == 1 :
    print(1)
else :
    dp = [0]*(n+1)
    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)

---

후기 

 앞선 11726 문제와 같이 규칙 찾기가 중요했었던 문제같다..!!