백준 14722번 우유 도시 :: 마이구미

이 글은 백준 알고리즘 문제 14722번 "우유 도시" 를 풀이한다.

14720번 "우유 축제" 에서 조금 더 심화된 문제라고 볼 수 있다.

그렇기에, 동적계획법을 통해 문제를 해결한다.

14722번 문제 - https://www.acmicpc.net/problem/14722

14720번 풀이 - http://mygumi.tistory.com/223

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다.

맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다.

이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다.

영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다. 

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다.

So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

우유 축제와 다른 점은 움직이는 경로가 1차원 배열에서 2차원 배열로 변했다.

즉, 단순히 오른쪽으로만 이동했다면, 이번 문제는 오른쪽과 아래쪽으로 이동할 수 있다.

기존의 점화식이였던 2차원 배열에서 3차원 배열로 전환하면 된다.

이전 점화식을 이해했다면, 충분히 이해하리라 생각한다.

dp[m][n][milk] = 좌표 (m,n) 가게까지 어떤 우유를 마셨을 때 우유의 최대 개수

코드를 보면 편의를 위해 0행과 0열을 미리 셋팅했다는 걸 참고바란다.

private void solve() {
    int n = sc.nextInt();
    int[][] array = new int[n][n];
    int[][][] dp = new int[n][n][3];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            array[i][j] = sc.nextInt();
        }
    }
 
    if (array[0][0] == 0) {
        dp[0][0][0] = 1;
    }
 
    // ----------------------초기 셋팅-----------------------------------
    for (int i = 1; i < n; i++) {
        int milk = array[0][i];
 
        dp[0][i][0] = milk == 0 ? dp[0][i - 1][2] + 1 : dp[0][i - 1][0];
        dp[0][i][1] = milk == 1 && dp[0][i][2] < dp[0][i][0] ? dp[0][i - 1][0] + 1 : dp[0][i - 1][1];
        dp[0][i][2] = milk == 2 && dp[0][i][0] < dp[0][i][1] ? dp[0][i - 1][1] + 1 : dp[0][i - 1][2];
    }
 
    for (int i = 1; i < n; i++) {
        int milk = array[i][0];
 
        dp[i][0][0] = milk == 0 ? dp[i - 1][0][2] + 1 : dp[i - 1][0][0];
        dp[i][0][1] = milk == 1 && dp[i][0][2] < dp[i][0][0] ? dp[i - 1][0][0] + 1 : dp[i - 1][0][1];
        dp[i][0][2] = milk == 2 && dp[i][0][0] < dp[i][0][1] ? dp[i - 1][0][1] + 1 : dp[i - 1][0][2];
    }
    // ---------------------------------------------------------------
 
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            int milk = array[i][j];
 
            dp[i][j][0] = milk == 0 
                ? Math.max(dp[i][j - 1][2] + 1, dp[i - 1][j][2] + 1)
                : Math.max(dp[i][j - 1][0], dp[i - 1][j][0]);
            dp[i][j][1] = milk == 1 && dp[i][j][2] < dp[i][j][0]
                ? Math.max(dp[i][j - 1][0] + 1, dp[i - 1][j][0] + 1)
                : Math.max(dp[i][j - 1][1], dp[i - 1][j][1]);
 
            dp[i][j][2] = milk == 2 && dp[i][j][0] < dp[i][j][1]
                ? Math.max(dp[i][j - 1][1] + 1, dp[i - 1][j][1] + 1)
                : Math.max(dp[i][j - 1][2], dp[i - 1][j][2]);
        }
    }
    System.out.println(Math.max(dp[n - 1][n - 1][0], Math.max(dp[n - 1][n - 1][1], dp[n - 1][n - 1][2])));
}