[DP/자바] 코드트리 IL. 2차원 최대 증가 수열

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

 

위 문제는 일정 규칙에 따라 이동한다고 가정할 때, 가장 많은 이동 수를 얻는 경우를 찾는 문제이다. 특정 위치에서 항상 최선인 경우가 명확하다면 그리디 알고리즘으로 풀 수 있겠지만, 이번 경우에서는 위치와 grid상의 숫자에 따라 최선인 상황이 매우 다이나믹하게 변동된다. 따라서 동적 계획법이 적합한 알고리즘일 것으로 예상할 수 있다.

 

문제 풀이

 

첫 번째 풀이는 틀린 풀이이다.

public class 이차원_최대_증가_수열 {
    private static int n, m;
    private static int[][] arr;
    private static int[][] dp;

    private static Queue<Integer> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // init
        dp[0][0] = 1;
        pq.add(-1);
        

        for (int i = 1; i < n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i < m; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i < n; i++) {
            if (arr[i][1] > arr[0][0]) {
                dp[i][1] = 2;
            }
        }
        for (int i = 1; i < m; i++) {
            if (arr[1][i] > arr[0][0]) {
                dp[1][i] = 2;
            }
        }

        // tabulation
        for (int i = 2; i < n; i++) {
            for (int j = 2; j < m; j++) {
                for (int k = 1; k < i; k++) {
                    for (int l = 1; l < j; l++) {
                        if (arr[i][j] > arr[k][l]) {
                            dp[i][j] = Math.max(dp[i][j], dp[k][l] + 1);
                            pq.add(-dp[i][j]);
                        }
                    }
                }
            }
        }

        System.out.println(-pq.poll());
    }
}

위 풀이의 경우, 이전에 닿지 않았던 항들에 대하여도 지속적으로 탐색하고 있어서 요구하지 않는 경우까지 전부 탐색하고 있다. 이는 규칙을 올바르게 준수하지 못한 로직이다.

 

아래는 두번째 시도한 로직이며, 정답을 받을 수 있는 로직이다.

public class Main {
    private static int n, m;
    private static int[][] arr;
    private static int[][] dp;

    private static Queue<Integer> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // init
        dp[0][0] = 1;
        pq.add(-1);


        // tabulation
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < i; k++) {
                    for (int l = 0; l < j; l++) {
                        if (arr[i][j] > arr[k][l]) {
                            if (dp[k][l] == 0) {
                                continue;
                            }

                            dp[i][j] = Math.max(dp[i][j], dp[k][l] + 1);
                            pq.add(-dp[i][j]);
                        }
                    }
                }
            }
        }

        System.out.println(-pq.poll());
    }
}

 

위에서는 닿지 못한 구역의 dp값에 대하여는 continue를 통해 패스할 수 있도록 처리하고 있다. 또한 문제 조건에서 1,1에서 시작이라 하여 0번째 column과 row에 대하여 별도로 처리중이었는데, continue를 이용함으로써 가장 첫 번째 column과 row에 대하여도 별도로 로직을 세우지 않아도 넘어갈 수 있게 되었다.