[python] 백준 1309번 - 동물원

1309번: 동물원 (acmicpc.net)

1309번: 동물원

[ ] [ ]  이렇게 칸이 주어졌을 때 

아예 안 고를 경우

왼쪽 고를 경우

오른쪽 고를 경우로 나눕니다

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0 for i in range(3)]for j in range(n+1)]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, n+1):
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]
    dp[i][0] %= 9901
    dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
    dp[i][1] %= 9901
    dp[i][2] = dp[i - 1][1] + dp[i - 1][0]
    dp[i][2] %= 9901

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

저거 dp에 넣을 때도 9901로 나눠줘야 메모리 초과 안 나오네용

ㅎㅎ 기쁜 소식ㅎ

을 전하는 자여~

오늘 꿈이 되게 슬픈 꿈이었어서 여운이 남아서 다시 이어자고 싶었는데

슬픈 거에 집중하다가 잠이 다 깨서 고냥 포기했는데

핀터레스트 들어가니까 어떻게 이런 사진이 딱 뜨네요 알고리즘 짱짱걸