[백준11727] / 2×n 타일링 2 - DP

 

백준 11727

 

 

푼 날짜 : 2024.07.24

푼 문제 : [11727] / 2×n 타일링 2

사용한 언어 : python

 

 

 

점화식:

dp[i] = dp[i−2]∗2+dp[i−1] (i≥2)

 

 

어떻게 구했냐면...

 

모를 땐 직접 그려보자

 

 

점화식 찾기..

(내)이해를 돕기위한 그림

 

 

(i-1) 에는 너비를 맞추기 위해 블록 하나(=> 2*1타일)씩을 붙일 수 있지만
(i-2) 에는 두 칸을 붙일 수 있으므로 x2를 해준다는 식으로 이해했다. (=> 2는 2*1타일과 2*2타일 두 개를 의미)

 

 

예를 들어 현재 주어진 수가 5라면 가로로 5칸을 차지한다.

이럴 경우 이전(i-1) 값인 4에는 1을 붙여야 5칸을 만들 수 있다.

그 이전(i-2) 값인 3에는 2를 붙여야 5칸을 만들 수 있다.

 

 

코드 :

import sys

N = int(sys.stdin.readline())
dp = [0 for _ in range(1000+1)]

dp[0] = 0
dp[1] = 1
dp[2] = 3
dp[3] = 5

for i in range(4, N+1):
    dp[i] = dp[i-2]*2 + dp[i-1]

print(dp[N]%10007)

 

 

+

이번 경우에는 

결과값만 바로 10007로 나누어 출력했다.

 

하지만 종종 수가 커지면 식이 맞아도 틀릴 수 있기 때문에

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

 

이렇게 계산 할 때 마다 나누어주는 것도 좋은 방법이다.