BOJ - 14722 - 우유 도시

import sys

def solution():
    N = int(sys.stdin.readline())
    milk = []
    for _ in range(N):
        milk.append(list(map(int, sys.stdin.readline().split())))
    dp = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]
    if milk[0][0] == 0: dp[0][0][0] = 1

    for i in range(1, N):
        m = milk[0][i]
        if m == 0:
            dp[0][i][0] = dp[0][i - 1][2] + 1
        else:
            dp[0][i][0] = dp[0][i - 1][0]

        if m == 1 and dp[0][i][2] < dp[0][i][0]:
            dp[0][i][1] = dp[0][i - 1][0] + 1
        else:
            dp[0][i][1] = dp[0][i - 1][1]

        if m == 2 and dp[0][i][0] < dp[0][i][1]:
            dp[0][i][2] = dp[0][i - 1][1] + 1
        else:
            dp[0][i][2] = dp[0][i - 1][2]

    for i in range(1, N):
        m = milk[i][0]
        if m == 0:
            dp[i][0][0] = dp[i-1][0][2] + 1
        else:
            dp[i][0][0] = dp[i-1][0][0]

        if m == 1 and dp[i][0][2] < dp[i][0][0]:
            dp[i][0][1] = dp[i - 1][0][0] + 1
        else:
            dp[i][0][1] = dp[i - 1][0][1]

        if m == 2 and dp[i][0][0] < dp[i][0][1]:
            dp[i][0][2] = dp[i - 1][0][1] + 1
        else:
            dp[i][0][2] = dp[i - 1][0][2]

    for i in range(1, N):
        for j in range(1, N):
            m = milk[i][j]

            if m == 0:
                dp[i][j][0] = max(dp[i][j - 1][2] + 1, dp[i - 1][j][2] + 1)
            else:
                dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0])

            if m == 1 and dp[i][j][2] < dp[i][j][0]:
                dp[i][j][1] = max(dp[i][j - 1][0] + 1, dp[i - 1][j][0] + 1)
            else:
                dp[i][j][1] = max(dp[i][j - 1][1], dp[i - 1][j][1])

            if m == 2 and dp[i][j][0] < dp[i][j][1]:
                dp[i][j][2] = max(dp[i][j - 1][1] + 1, dp[i - 1][j][1] + 1)
            else:
                dp[i][j][2] = max(dp[i][j - 1][2], dp[i - 1][j][2])

    print(max(dp[-1][-1][0], dp[-1][-1][1], dp[-1][-1][2]))
solution()

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