[dp] 17069번 백준 파이프 옮기기2

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

17069번: 파이프 옮기기 2

 

한 지점(y,x)에 가로로 도달했다면 - 가로로 (y, x+1)에 도달할 수 있고, 대각선으로 (y+1, x+1)에 도달할 수 있다.

세로와 대각선도 마찬가지다.

(y,x)에 세로로 도달 -> 세로로 (y+1, x)에 도달, 대각선으로 (y+1, x+1)에 도달

(y,x)에 대각선으로 도달 -> 가로로 (y, x+1)에 도달, 세로로 (y+1, x)에 도달, 대각선으로 (y+1, x+1)에 도달

 

 

이때, dp[0][y][x] : (y,x)에 가로로 도달하는 경우의 수

dp[1][y][x] : (y,x)에 세로로 도달하는 경우의 수

dp[2][y][x] : (y,x)에 대각선으로 도달하는 경우의 수 라고 가정한다.

 

 

위의 규칙을 식으로 정리하면

dp[0][y][x+1] = dp[0][y][x] + dp[2][y][x]

dp[1][y+1][x] = dp[1][y][x] + dp[2][y][x]

dp[2][y+1][x+1] = dp[0][y][x] + dp[1][y][x] + dp[2][y][x]

 

import sys

N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[[0]*N for _ in range(N)] for _ in range(3)]

dp[0][0][1]=1

for x in range(2, N):
    if graph[0][x]==0:
        dp[0][0][x] = dp[0][0][x-1]

for y in range(1, N):
    for x in range(1, N):
        if x<N and graph[y][x]==0:
            dp[0][y][x] = dp[0][y][x-1] + dp[2][y][x-1]
        if y<N and graph[y][x]==0:
            dp[1][y][x] = dp[1][y-1][x] + dp[2][y-1][x]
        if y<N and x<N and graph[y][x]==0 and graph[y][x-1]==0 and graph[y-1][x]==0:
            dp[2][y][x] = dp[0][y-1][x-1] + dp[1][y-1][x-1] + dp[2][y-1][x-1]
print(dp[0][-1][-1]+dp[1][-1][-1]+dp[2][-1][-1])