[백준BOJ] 11727번 2xn 타일링2.py

 

백준 저지에서 2xn 타일링2를 파이썬을 통해 풀어 보았다. 

 

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

11727번: 2×n 타일링 2

11727번 2xn 타일링2.py

tomy9729/Algorithm

 

 

1259번 팰린드롬수

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.

설명

dp문제이다. 2xn 직사각형이 2x(n-1) 직사각형과 2x(n-2)와 어떤 관계인지 파악해야 풀 수 있다. 다음과 같이 2xn 직사각형이 있다고 가정하자. 2xn직사각형에 대해 타일로 채우는 방법의 수를 저장하는 배열 dp를 생성한다. dp[1]과 dp[2]는 직접 계산하여 각각 1,3으로 구할 수 있다.

n직사각형을 만들기 위해서는 (n-1)직사각형에서 1x2 타일을 채우는 경우가 있다. 즉 dp[n-1]*dp[1]이다.

또는 (n-2)직사각형에서 타일들로 채우는 경우가 있다. 즉 dp[n-2]*dp[2]이다.

이 때 두 경우에 대해 중복되는 경우가 발생한다. 

 

위 그림과 같이 나오는 경우가 위 두개의 경우에서 중복된다. 중복되는 경우의 수는 dp[n-2]만큼 존재한다. 

 

위 사실을 통해 다음과 같은 점화식을 도출할 수 있다.

 

dp[n] = dp[n-1]*dp[1] + dp[n-2]*dp[2] - dp[n-2]

 

점화식을 바탕으로 동적 계획법 알고리즘을 작성할 수 있다. 

코드

#11727번 2xn 타일링2.py
if __name__ == "__main__":
  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]*dp[1]+dp[i-2]*(dp[2]-1))%10007
    print(dp[n])