출발 조건이 까다로운 2차원 배열 목적지까지 이동하는 다이나믹 프로그래밍

14722번: 우유 도시

 

(0,0)에서 (n-1,n-1)까지 이동하면서 우유를 마시는데

 

맨 처음에는 딸기우유를 마신다

 

딸기우유를 마신 다음에 초코우유를 마신다

 

초코우유를 마신 다음에 바나나 우유를 마신다

 

바나나 우유를 마신 다음에 딸기 우유를 마신다

 

위 4가지 조건을 만족하면서 우유를 마시는데, (x,y)에는 딸기, 초코, 바나나 우유 셋 중 하나만 있다.

 

최대로 마실 수 있는 우유 개수는?

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

dp[i][j][k] = (j,i)에 있는데 마지막으로 k 우유를 먹었을때, 그동안 최대로 마신 우유 개수로 설정하면

 

조건에 맞게 식을 세우는건 쉬울텐데

 

핵심은 맨 처음에 딸기 우유를 마신다는 것

 

그런데 (0,0)에서 출발을 할건데 문제는 (0,0)에 딸기 우유가 있다는 보장이 없음

 

즉 dp[0][0][0] = 1이라는 보장은 없다

 

초기화를 어떻게 해야하냐가 문제인데 그냥 모든 (x,y)에 대하여 dp[y][x][0] = 1로 초기화해두고

 

from sys import stdin

n = int(stdin.readline())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

#dp[i][j][k] = (j,i)에서 마지막으로 k번째 우유를 마실때 그 동안 최대로 마신 우유의 개수
dp = [[[0]*3 for _ in  range(n)] for _ in range(n)]

#맨 처음에 딸기 우유를 마신다
#초기화
#일단 딸기우유인 곳에서 dp[y][x][0] = 1로 해두고

for y in range(n):
    
    for x in range(n):
        
        if maps[y][x] == 0:
            
            dp[y][x][0] = 1

 

 

다이나믹 프로그래밍으로 계산하면 > 0인 부분만 개수를 세어나가니까 알아서 최댓값이 갱신되어나갈테고

 

동쪽과 남쪽만으로 움직일 수 있으니까 편의를 위해

 

y = 0인 경우 동쪽 방향으로 먼저 초기화하고

 

(0,x)에 왔을 때 우유를 안마시는 경우는 dp[0][x][i] = max(dp[0][x][i], dp[0][x-1][i])

 

우유를 마시는 경우는 maps[0][x]값에 따라서...

 

딸기우유를 마셔야하는 경우는 이전에 바나나 우유를 마셔야하고,

 

여기서 문제는 dp[0][x-1][2] >= 1인 경우에만 이라는거 

 

dp[0][x-1][2] = 0인 경우는 그동안 우유를 마셔본적이 없는거기 때문에 조건에 맞지 않다

 

왜냐하면 맨 처음에 반드시 딸기우유를 먼저 마셨기 때문

 

바나나우유, 초코우유도 마찬가지로 계산가능

 

for x in range(1,n):
    
    for i in range(3):
        
        dp[0][x][i] = max(dp[0][x][i],dp[0][x-1][i])

    if maps[0][x] == 0:
        
        if dp[0][x-1][2] >= 1:

            dp[0][x][0] = max(dp[0][x][0],dp[0][x-1][2] + 1)
    
    elif maps[0][x] == 1:
        
        if dp[0][x-1][0] >= 1:

            dp[0][x][1] = max(dp[0][x][1],dp[0][x-1][0] + 1)
    
    else:
        
        if dp[0][x-1][1] >= 1:

            dp[0][x][2] = max(dp[0][x][2],dp[0][x-1][1] + 1)

 

 

x = 0인 경우 y방향에 대해서도 마찬가지로 초기화

 

for y in range(1,n):
    
    for i in range(3):
            
        dp[y][0][i] = max(dp[y][0][i], dp[y-1][0][i])
    
    if maps[y][0] == 0:
        
        if dp[y-1][0][2] >= 1:

            dp[y][0][0] = max(dp[y][0][0], dp[y-1][0][2] + 1)
    
    elif maps[y][0] == 1:
        
        if dp[y-1][0][0] >= 1:

            dp[y][0][1] = max(dp[y][0][1], dp[y-1][0][0] + 1)
    
    else:
        
        if dp[y-1][0][1] >= 1:

            dp[y][0][2] = max(dp[y][0][2], dp[y-1][0][1] + 1)

 

 

그리고 (1,1)부터 시작해서 (n-1,n-1)까지에 대해서는...

 

(x,y)에 도달했을 때 i번째 우유를 마시지 않는 경우는...

 

(x,y)에 도달 가능한 경우는 (x-1,y)와 (x,y-1)에 대해서 dp[y][x][i] = max(dp[y][x-1][i], dp[y-1][x][i])

 

i번째 우유를 마셔야하는 경우는...

 

maps[y][x] 값에 따라서 딸기 우유라면.. 이전에 바나나우유를 마셔야하므로

 

dp[y][x][0] = max(dp[y][x]0], dp[y][x-1][2] + 1, dp[y-1][x][2] + 1)

 

당연히 dp[y][x-1][2]와 dp[y-1][x][2]는 1이상이어야한다.

 

0인 경우는 처음에 딸기우유를 안마셨다는 뜻이니까

 

나머지 바나나우유, 초코우유도 마찬가지

 

for y in range(1,n):
    
    for x in range(1,n):
        
        for i in range(3):
                
            dp[y][x][i] = max(dp[y][x][i], dp[y][x-1][i], dp[y-1][x][i])
        
        if maps[y][x] == 0:
            
            if dp[y-1][x][2] >= 1:

                dp[y][x][0] = max(dp[y-1][x][2] + 1, dp[y][x][0])
            
            if dp[y][x-1][2] >= 1:
                
                dp[y][x][0] = max(dp[y][x-1][2] + 1, dp[y][x][0])

        elif maps[y][x] == 1:
            
            if dp[y][x-1][0] >= 1:

                dp[y][x][1] = max(dp[y][x-1][0] + 1, dp[y][x][1])
            
            if dp[y-1][x][0] >= 1:
                
                dp[y][x][1] = max(dp[y-1][x][0] + 1, dp[y][x][1])

        elif maps[y][x] == 2:
            
            if dp[y][x-1][1] >= 1:

                dp[y][x][2] = max(dp[y][x-1][1] + 1, dp[y][x][2])
            
            if dp[y-1][x][1] >= 1:
                
                dp[y][x][2] = max(dp[y-1][x][1] + 1, dp[y][x][2])

print(max(dp[n-1][n-1]))

 

 

정답은 dp[n-1][n-1][0], dp[n-1][n-1][1], dp[n-1][n-1][2]중 최댓값을 찾는다

 

핵심은 처음에 출발조건을 어떻게 설정하냐이거라서

 

dp[0][0][0] = 1이 아니라 모든 (x,y)에 대해 dp[y][x][0] = 1로 설정했다는거