문제 링크
https://www.acmicpc.net/problem/11727
잡담
갑자기 이런 것이 생겼다. 언제부터 생긴 건지는 모르겠지만 일단 생겼길래 다 풀고 두 문제만 포스팅하려 한다.
구현 과정
처음부터 대충 n에 따른 정답을 계산해봤더니 다음과 같이 나왔다.
$S(1) = 1$
$S(2) = 3$
$S(3) = 5$
$S(4) = 11$
.
.
.
보아하니 다음과 같은 식을 따르는 것 같다.
$S(n) = S(n - 1) + 2 \cdot S(n - 2)$
그래서 재귀 돌렸다. 기억하면서.
코드
dp = dict()
def recur(n: int)->int:
if n == 1: return 1
elif n == 2: return 3
else:
if n not in dp.keys(): dp[n] = 2 * recur(n - 2) + recur(n - 1)
return dp[n]
n = int(input())
print(recur(n) % 10007)