[백준 12849번] 본대 산책 (Python3)

import sys
input = sys.stdin.readline
mod = 1000000007

D = int(input())

graph = [[0]*8 for i in range(8)]

graph[0][1] = graph[0][2] = 1
graph[1][0] = graph[1][2] = graph[1][3] = 1
graph[2][0] = graph[2][1] = graph[2][3] = graph[2][4] = 1
graph[3][1] = graph[3][2] = graph[3][4] = graph[3][5] = 1
graph[4][2] = graph[4][3] = graph[4][5] = graph[4][7] = 1
graph[5][3] = graph[5][4] = graph[5][6] = 1
graph[6][5] = graph[6][7] = 1
graph[7][4] = graph[7][6] = 1


DP = [[0]*(D+1) for i in range(8)]
DP[0][0] = 1

for i in range(1,D+1):
  for now in range(8):
    for last in range(8):
      if graph[now][last]:
        DP[now][i] += DP[last][i-1]%mod

print(DP[0][-1]%mod)

 

본대 산책 2의 풀이가 도저히 안떠올라서 본대 산책 1을 먼저 풀어보기로 했다.

난이도는 실버1로 매우 쉽다.

 

그냥 단순 DP이다.

 

 

오늘의 교훈) 본대 산책 2를 풀어보자