[백준] 14722 우유 도시 - Java

 

 

 

문제 출저

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

14722번: 우유 도시

 

 

 

 

문제 풀이

딸기 (0) -> 초코 (1) -> (2) 바나나 순서로 우유를 마셔야 한다. 

즉 딸기를 먼저 마셔야 한다. 동쪽, 남쪽으로만 이동할 수 있다. 

 

3차원 dp 배열을 사용한다. dp[ y 위치 ][ x 위치 ][ 우유 종류 ] 

현재 위치의 우유를 기준으로 서쪽, 북쪽의 이전 단계의 우유에 +1과 현재 우유의 크기를 비교하여 큰 것을 저장한다. 

// 딸기 우유 마시기
if(board[i][j] == 0) {
    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j][2] + 1);
    dp[i][j][0] = Math.max(dp[i][j][0], dp[i][j-1][2] + 1);
}

 

 

여기서, 바나나 우유와 초코 우유는 앞에 반드시 마셔야 한다. 

그러므로 조건문을 추가하여 앞에 우유를 마신 적이 없다면 dp 계산을 제외한다. 

// 바나나 우유 마시기, 이 전에 딸기 우유를 마셔야 한다.
if(board[i][j] == 1) {
    if (dp[i-1][j][0] != 0) dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][0] + 1);
    if (dp[i][j-1][0] != 0) dp[i][j][1] = Math.max(dp[i][j][1], dp[i][j-1][0] + 1);
}

 

 

정답은 도착 지점의 모든 종류를 비교하여 큰 값을 선택한다. 

int answer = dp[n][n][0];
for (int i = 0; i < 3; i++) {
    answer = Math.max(answer, dp[n][n][i]);
}

 

 

 

 

소스 코드

mport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
우유 도시
https://www.acmicpc.net/problem/14722

0 : 딸기 우유
1 : 초코 우유
2 : 바나나 우유

딸기 우유 -> 초코 우유 -> 바나나 우유 -> 딸기 우유
안 마실 수도 있음

딸기 우유 먼저 시작해야 한다.




 */

public class Main {

    static int n;
    static int[][] board;
    static int[][][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new int[n+1][n+1][3];


        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {

                // 안 마신 경우
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j][k]);
                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j-1][k]);
                }


                // 딸기 우유 마시기
                if(board[i][j] == 0) {
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j][2] + 1);
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i][j-1][2] + 1);
                }

                // 바나나 우유 마시기, 이 전에 딸기 우유를 마셔야 한다.
                if(board[i][j] == 1) {
                    if (dp[i-1][j][0] != 0) dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][0] + 1);
                    if (dp[i][j-1][0] != 0) dp[i][j][1] = Math.max(dp[i][j][1], dp[i][j-1][0] + 1);
                }

                // 초코 우유 마시기, 이 전에 바나나 우유를 마셔야 한다.
                if(board[i][j] == 2) {
                    if (dp[i-1][j][1] != 0) dp[i][j][2] = Math.max(dp[i][j][2], dp[i-1][j][1] + 1);
                    if (dp[i][j-1][1] != 0) dp[i][j][2] = Math.max(dp[i][j][2], dp[i][j-1][1] + 1);
                }

            }
        }


        int answer = dp[n][n][0];
        for (int i = 0; i < 3; i++) {
            answer = Math.max(answer, dp[n][n][i]);
        }

        System.out.println(answer);

    }

}