백준 14722 JAVA : 우유 도시

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

14722번: 우유 도시

 

---

풀이방법

bfs로 풀었다가.. 메모리초과 빔 맞음.. 그래서 생각한 dp풀이

dp[i][j][k] -> i,j 위치에 있는 k 우유를 마셨을 때 우유의 최대 개수

 

1. 내 기준으로 동쪽, 남쪽을 본다.

2. 현재 위치의 색이 0 이면(딸기우유) 1과 현재 값 중 큰 값을 넣어준다. => 딸기우유가 처음이 아닐 경우를 고려

3. 현재 위치를 기준으로 동쪽우유를 본다 => 현재 위치값과 동쪽값 중 큰 값을 넣는다.

4. 현재 위치의 값이 0 보다 크면 (첫 딸기우유를 이미 먹었던 상태) 현재위치의 우유와 동쪽 위치의 우유가 순서가 맞는지 본다. => ex. 현재 : 2 동쪽 : 0 , 현재 : 1 동쪽 : 2, 현재 : 0 동쪽:1 

5. 순서가 맞다면 동쪽 값에 현재+1 값 과 기존 동쪽 값을 비교해서 큰 값을 넣는다.

6. 남쪽도 동일하게 로직 작성

7. dp[N-1][N-1][0], dp[N-1][N-1][1], dp[N-1][N-1][2] 중 큰 값을 출력한다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N; //우유도시 영역 크기
    static int milk[][];
    static int dp[][][];


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        milk = new int[N+1][N+1];
        dp = new int[N+1][N+1][3]; //좌표 (x,y)까지 어떤 우유를 마셨을 때 우유의 최대 개수

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                milk[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //딸기->초코->바나나->딸기


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int color = milk[i][j];

                if(color == 0) {//현재 위치의 색이 0 이면, 1과 기존값 중 큰 값으로 시작 -> 딸기우유부터 시작해야하기 때문
                    dp[i][j][0] = Math.max(1,dp[i][j][0]);
                }

                int colorN = milk[i+1][j]; // 내 기준 남쪽 우유 -> 0: 딸기, 1: 초코, 2: 바나나
                int colorE = milk[i][j+1]; // 내 기준 동쪽 우유 -> 0: 딸기, 1: 초코, 2: 바나나

                dp[i+1][j][0] = Math.max(dp[i][j][0], dp[i+1][j][0]); //남쪽에 기존값과 내 현재값 중 큰 값을 넣어줌
                dp[i][j+1][0] = Math.max(dp[i][j][0],dp[i][j+1][0]); //동쪽에 기존값과 내 현재값 중 큰 값을 넣어줌

                dp[i+1][j][1] = Math.max(dp[i][j][1], dp[i+1][j][1]);
                dp[i][j+1][1] = Math.max(dp[i][j][1],dp[i][j+1][1]);

                dp[i+1][j][2] = Math.max(dp[i][j][2], dp[i+1][j][2]);
                dp[i][j+1][2] = Math.max(dp[i][j][2],dp[i][j+1][2]);

                //남쪽,동쪽
                if(dp[i][j][2] > 0 ) { //기존 값이 있으면(딸기우유 부터 시작해야해서 0 이면 값 갱신 못하도록)
                    if (colorN == 0) { //남쪽의 우유가 딸기우유면 (현재 : 바나나)
                        dp[i+1][j][0] = Math.max(dp[i][j][2]+1, dp[i+1][j][0]); //현재값 +1 과 기존 값을 비교 후 큰 값 반영
                    }
                    if (colorE == 0) { //동쪽도 같은 원리
                        dp[i][j+1][0] = Math.max(dp[i][j][2]+1, dp[i][j+1][0]);
                    }
                }

                if(dp[i][j][0] > 0 ) {
                    if (colorN == 1) {
                        dp[i+1][j][1] = Math.max(dp[i][j][0]+1, dp[i+1][j][1]);
                    }
                    if (colorE == 1) {
                        dp[i][j+1][1] = Math.max(dp[i][j][0]+1, dp[i][j+1][1]);
                    }
                }

                if(dp[i][j][1] > 0) {
                    if (colorN == 2) {
                        dp[i+1][j][2] = Math.max(dp[i][j][1]+1, dp[i+1][j][2]);
                    }
                    if (colorE == 2) {
                        dp[i][j+1][2] = Math.max(dp[i][j][1]+1, dp[i][j+1][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])));

    }
}

 

 

결과