Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-17070-파이프 옮기기 1

import sys
input = sys.stdin.readline

N = int(input())
maps = [[1 for _ in range(N+1)] for _ in range(N+1)]

# build map
for i in range(1, N+1):
    row = list(map(int, input().split()))
    for j in range(1, N+1):
        maps[i][j] = row[j-1]

# Use dynamic programming
dp_right = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp_diag = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp_down = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        # dp right
        if maps[i][j] == 0:
            if i == 1 and j == 1: # initialize
                dp_right[i][j] = 0
            elif i == 1 and j == 2:
                dp_right[i][j] = 1
            else:
                dp_right[i][j] = dp_right[i][j-1] + dp_diag[i][j-1]

        # dp down
        if maps[i][j] == 0:
            dp_down[i][j] = dp_down[i-1][j] + dp_diag[i-1][j]

        # dp diag
        if maps[i][j] == 0 and maps[i-1][j] == 0 and maps[i][j-1] == 0:
            dp_diag[i][j] = dp_right[i-1][j-1] +  dp_diag[i-1][j-1] + dp_down[i-1][j-1]

print(dp_right[N][N] + dp_down[N][N] + dp_diag[N][N])
Comments