728x90
기존 문제의 응용문제다.
점화식 정의는 기존과 동일하다.
dp[i] : 2xi 크기의 타일을 채우는 모든 경우의 수
하지만 이번에는 2x2 공간에 대해 1x2 뿐만 아니라 2x2으로도 채울 수 있다.
n = 1 일때 1 : 2x1
n = 2 일때 3 : 2x1, 1x2, 2x2
마찬가지로 n >= 3 부터는 아래의 점화식이 성립한다.
dp[i-1] = 2x1 1개
dp[i-2] = 1x2 2개
dp[i-2] = 2x2 1개
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 2]
문제 조건에 따라 MOD(10,007)로 나눈 값을 dp에 담아주자.
소스코드
출처
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 30958] 서울사이버대학을 다니고 [Python] (0) | 2024.07.28 |
---|---|
[백준 06438] Reverse Text [Python] (0) | 2024.07.26 |
[백준 15083] Life Savings [Python] (0) | 2024.07.25 |
[백준 01932] 정수 삼각형 [Python] (0) | 2024.07.24 |
[백준 06437] Golf [Python] (2) | 2024.07.24 |