17070_파이프옮기기

🍯 DP 포인트

• 이전에 어떤 파이프방식으로 끝났느냐에 따라서, 이번 칸으로 올 수 있는 경우의 수가 달라진다!
• 대각선으로 올 수 있는건 추가적인 조건제한이 필요함

🗨️ Comment

• 3차원 dp배열을 처음 풀어봄.
• 기본은 2차원 배열인데, 각 원소에 대해 접근케이스가 3가지로 나뉘니까 3차원을 떠올려야 한다

# 1초 / 512MB
# 23.05.20
# 11:45 ~ 12:14 / 15:40 ~ 

N = int(input()) # N * N 
mat = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N):
    if mat[0][i] != 1:
        dp[0][0][i] = 1
    else:
        break 

# dp 
for r in range(1, N):
    for c in range(1, N):
        # 해당 지점에 대각선으로도 올 수 있는지 
        if mat[r][c] != 1 and mat[r-1][c] == 0 and mat[r][c-1] == 0:
            # 대각선포함해서 가능
            dp[1][r][c] = dp[0][r-1][c-1] + dp[1][r-1][c-1]  + dp[2][r-1][c-1]

        # 대각선으로는 못오면
        if mat[r][c] != 1:
            dp[0][r][c] = dp[0][r][c-1] + dp[1][r][c-1] 
            dp[2][r][c] = dp[2][r-1][c] + dp[1][r-1][c]
print(dp[0][N-1][N-1] + dp[1][N-1][N-1] + dp[2][N-1][N-1])