파이썬) 2 X N 타일링 - BOJ

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

n = int(input())

dp = [0] * 1001

dp[1] = 1
dp[2] = 2
dp[3] = 3


if n <= 3:
    print(dp[n])
else:

    for i in range(4, 1001):
        dp[i] = (dp[i-1] + dp[i-2]) % 10007

    print(dp[n])

 

풀이법

풀이법은 의외로 간단하다.

우선 n이 1인 경우를 생각해보자

 

여기선 2 x 1짜리 하나가 들어가니까 정답은 1이다.

2x2인 경우 1x2 두개와 2x1두개. 즉 정답은 2이다.

그렇다면 3의 경우는 어떨까

3의 경우는 좀 다르게 바라볼 필요가 있다.

 

2x 1과 2x2를 합친게 2x3이다.

잘 생각해보자 2x1의 경우의 정답은 1이다. 그리고 2x2의 정답은 2이다. 그렇다면 2x3또한 1x2와 2x2칸으로 나누어보면 결국 앞선 두 경우의 정답을 더한 것이 2 x 3의 정답이 된다.