1309번 파이썬

4번째까지 다 그려봤는데 n-1번째 p값에 x3한 값을 n-2번째부터 1번째까지의 값을 빼주면 정답이 나오는 것 같아서 그런식으로 코드를 만들어봤는데 시간 초과 에러만 뜬다,,

import sys
input = sys.stdin.readline
n=int(input())
p = [0 for _ in range(n+1)]

if n >=1:
  p[1]=2
if n >=2:
  p[2]=6
sum=0
for num in range(3,n+1):
  p[num]+=p[num-1]*3
  sum+=p[num-2]
  p[num]-=sum
print((p[n]+1)%9901)

 

그래서 다른 사람 방식 봤더니 다들 완전 쉽게 생각해서 푼것 같다. 굳이 전부 다 안그려봐도 0=>사자를 안놨을때 1-> 왼쪽에 놨을때 2-> 오른쪽에 놨을때의 경우로 생각해서 1과 2인 경우는 서로 겹치지 않게 이전 값을 더하면 쉽게 답이 나온다..!

 

 

import sys
input = sys.stdin.readline
n=int(input())
p = [[0,0,0] for _ in range(n+1)]

p[1][0]=1
p[1][1]=1
p[1][2]=1
for num in range(2,n+1):
  p[num][0]=(p[num-1][0]+p[num-1][1]+p[num-1][2])%9901
  p[num][1]=(p[num-1][0]+p[num-1][2])%9901
  p[num][2]=(p[num-1][0]+p[num-1][1])%9901
print(sum(p[n])%9901)