# BOJ - 14722 - 우유 도시

Updated:

``````import sys

def solution():
milk = []
for _ in range(N):
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

Categories:

Updated: