정답
def _1309() :
N = int(input())
DP = [0]*(N+1)
DP[0] = 1
DP[1] = 3
for i in range(2, N+1) :
DP[i] = (DP[i-1] + 2*DP[i-2] + (DP[i-1]-DP[i-2]))%9901
print(DP[N])
_1309()
풀이
구글링을 통해 보다 내 코드보다 이해하기 쉬운 코드를 찾았다.
s[n][0]은 사자우리 배열의 끝에 사자가 없는 경우,
s[n][1]은 사자우리 배열의 끝 중 왼쪽에 사자가 있는 경우,
s[n][2]은 사자우리 배열의 끝 중 오른쪽에 사자가 있는 경우를 의미한다.
이렇게 생각해보면, n=1일 때, 즉 2*1 사이즈의 배열에 사자를 넣을 때에,
s[1][0] = 1
s[1][1] = 1
s[1][2] = 1
으로 사자가 없는 경우, 왼쪽에 사자가 있는 경우, 오른쪽에 사자가 있는 경우가 있다. 이를 기반으로 2*2 사이즈의 배열도 구해보자면,
# 사자가 있든 없든, 사자가 없는 우리를 한 행 추가할 수 있음
s[2][0] = s[1][0] + s[1][1] + s[1][2]
# 사자를 왼쪽에 넣기 위해선, 사자가 없는 것으로 끝나거나 사자가 오른쪽에 있는 것으로 끝나야한다.
s[2][1] = s[1][0] + s[1][2]
# 사자를 오른쪽에 넣기 위해선, 사자가 없는 것으로 끝나거나 사자가 왼쪽에 있는 것으로 끝나야한다.
s[2][2] = s[1][0] + s[1][1]
으로 구할 수 있다.
이렇게 등장하는 점화식은 다음과 같다.
for i in range(2, 100001) :
s[i][0] = (s[i-1][0] + s[i-1][1] + s[i-1][2])%9901
s[i][1] = (s[i-1][0] + s[i-1])%9901
s[i][2] = (s[i-1][1] + s[i-1][2])%9901
print(sum(s[n])%9901)