문제

https://www.acmicpc.net/problem/1309

나의 코드

from sys import stdin
input = stdin.readline

n = int(input())
dp = [ [0] * 3 for _ in range(100000+1) ]
for i in range(3):
    dp[1][i] = 1 # n이 1일때 [아무것도 선택하지 않는 경우, 첫번째 열 선택, 두번째 열 선택]

for i in range(2, 100000+1):

    # i가 2라면
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901 # i가 1일때 값들을 불러옴
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901 # 아무것도 선택하지 않는 경우 + 두번째 열을 선택하는 경우
    dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901 # 아무것도 선택하지 않는 경우 + 첫번째 열을 선택하는 경우

print(sum(dp[n]) % 9901)

    

느낀점

DP의 정의인 이전 값에 대한 값을 불러올 수 있어야 한다.

참고 자료

https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-1309-%EB%8F%99%EB%AC%BC%EC%9B%90-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python