백준 17070 [파이프 옮기기 1] 파이썬

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

 

#백준 17070 파이프 옮기기 1
import sys
input = sys.stdin.readline

N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0]*3 for _ in range(N)] for _ in range(N)]

# 초기 위치 (0,1)에 가로 방향 파이프가 한 개 있음
dp[0][1][0] = 1

for i in range(N):
    for j in range(2, N):  # (0,1)부터 시작하므로 j는 2부터
        if maps[i][j] == 1:
            continue

        # 가로
        dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2] if maps[i][j-1] == 0 else 0

        # 세로
        if i > 0:
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2] if maps[i-1][j] == 0 else 0

        # 대각선
        if i > 0 and maps[i-1][j] == 0 and maps[i][j-1] == 0 and maps[i-1][j-1] == 0:
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

# 정답은 (N-1,N-1) 위치의 3방향 합
print(dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2])

3차원 배열 생각했는데, 아쉽다...

문제에서 알려준대로 짜기만하면 됐는데, 너무 복잡하게 생각했다.