이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 찾는 과정이 정말 오래 걸렸다. 결국은 구글링을 통해 점화식을 찾아 겨우 해결할 수 있었다. 이 문제 점화식의 핵심은 맨 위에 두 칸중 사자가 어디에 있는지에 따라서 따로따로 메모라이제이션을 해야한다는 점이었다.

본인은 dp를 3차원 배열로 만들고 dp[n][0]은 위의 두 칸 중에서 왼쪽에 사자가 있을 경우, dp[n][1]은 위의 두 칸 중에서 오른쪽에 사자가 있을 경우, dp[n][2]는 위의 두 칸 중에서 사자가 어느쪽에도 없을 경우로 설정하였다.

		1	2	3	4

dp[i][0]	1	2	5	12
dp[i][1]	1	2	5	12
dp[i][2]	1	3	7	17

위와 같이 dp[i][0]은 dp[i-1][1]+dp[i-1][2]의 값을 가지게 되고, dp[i][1]은 dp[i-1][2]+dp[i-1][0]의 값을 가지게 되고, dp[i][2]는 dp[i-1][0]+dp[i-1][1]+dp[i-1][2]의 값을 가지게 된다.

이 문제에서 n의 값이 커지면 커질 수록 수가 급격하게 커지기 때문에 매 반복마다 dp를 구할 때에 %9901연산을 계속해서 진행해주어야 한다. 이를 안할 경우 메모리 초과 에러가 발생하게 된다.

결과적으로 점화식은

dp[n]=(dp[n-1][0]+dp[n-1][1]) + (dp[n-1][2]+dp[n-1][0]) + (dp[n-1][0]+dp[n-1][1]+dp[n-1][2])

로 구할 수 있다.

• n을 입력받는다.
• dp를 0으로된 3차원 배열을 만든다.
• 3만큼 반복하는 i에 대한 for문을 돌린다.
  -> dp[1][i]를 1로 갱신한다.
• 2부터 n까지의 i에 대한 for문을 돌린다.
  -> dp[i][0]을 (dp[i-1][1]+dp[i-1][2])%9901로 갱신한다.
  -> dp[i][1]을 (dp[i-1][2]+dp[i-1][0])%9901으로 갱신한다.
  -> dp[i][2]를 (dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901로 갱신한다.
• dp[n] 배열을 모두 더한 값에 9901을 나눈 나머지를 출력한다.

Code

n=int(input())
dp=[[0]*3 for _ in range(n+1)]
for i in range(3):
    dp[1][i]=1
for i in range(2, n+1):
    dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901
    dp[i][1]=(dp[i-1][2]+dp[i-1][0])%9901
    dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901
print(sum(dp[n])%9901)