[Java] 백준 14722번 : 우유 도시

1. 문제

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

14722번: 우유 도시

 

 

2. 풀이 과정

배열의 크기가 1000x1000이므로, DFS와 같은 완탐으로는 시간 초과가 날 것 같아서 DP로 시도했다.

아직 DP문제는 푸는 데 시간이 좀 걸린다..

 

딸기 우유, 초코 우유, 바나나 우유 3가지 경우를 나눠서 생각하기 위해서 DP를 3차원 배열로 구현했다.

중간에 안 먹고 건너 뛸 수도 있어서 마지막에 어떤 종류를 먹었는지를 고려해주기 위해서다.

전체 배열을 2차원 배열로 탐색 + 우유 종류마다 반복문을 돌면서 자신의 위쪽과 왼쪽의 값 중 최댓값을 가져오며, 현재 위치에서 하나를 더 먹으면 최대가 되는지 확인하고 반영해주었다. 

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

public class Main {
    static int N;
    static int[][] map;
    static int[][][] result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        result = new int[N][N][3];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = st.nextToken().charAt(0) - '0';
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                int prev = (map[i][j] + 2)%3;
                int x = i - 1;
                int y = j - 1;
                for(int k=0; k<=2; k++){
                    result[i][j][k] = Math.max(0<=x ? result[x][j][k] : 0, 0<=y ? result[i][y][k] : 0);
                }
                if(result[i][j][prev]> 0){
                    result[i][j][map[i][j]] = Math.max(result[i][j][map[i][j]], result[i][j][prev] + 1);
                }

                if(map[i][j] == 0 && result[i][j][0] == 0){
                    result[i][j][0] = 1;
                }

            }
        }
        System.out.println(Math.max(Math.max(result[N-1][N-1][0], result[N-1][N-1][1]), result[N-1][N-1][2]));
    }

}

 

 

결과