import sys
input = sys.stdin.readline
mod_num = 10_007
def BOJ11727() :
n = int(input())
dp = [0 for _ in range(1001)]
dp[1] = 1
dp[2] = 3
for i in range(3, 1001) :
dp[i] = ((dp[i-2] * 2) % mod_num + (dp[i-1]) % mod_num) % mod_num
print(dp[n])
BOJ11727()
접근 방법
1. 3번째 인덱스부터 도형을 그리려면 n-1 번째에서는 [2x1] 타일밖에 이용을 할 수가 없다.
n-2 번째에서는 [1x2] 두개, [2x2] 하나를 이용하는 방법 두개씩 가능하다
이를 점화식으로 나타내면
dp[n] = dp[n-2] * 2 + dp[n-1] 이 된다.
나머지 연산만 분배법칙에 따라 적용해주면 된다.
https://www.acmicpc.net/problem/11727
'알고리즘' 카테고리의 다른 글
오르막 수[백준 11057] - python (0) | 2022.03.11 |
---|---|
퇴사 [백준 14501] - python (0) | 2022.03.10 |
이친수 [백준 2193] - python (0) | 2022.03.08 |
쉬운 계단 수 [백준 10844] - python (0) | 2022.03.07 |
포도주 시식[백준 2156] - python (0) | 2022.03.06 |