[DP/자바] 코드트리 IL. 정수 사각형 최대 합

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

문제 해석

이 문제는 N x N 행렬 위에서 이동을 할 때, 지나온 숫자들의 합이 최대가 되는 경우의 그 총합을 구하는 문제이다.

 

1. 완전탐색으로 접근했을 때 가능한가?

-> 일단 인접한 항으로 이동하면서 탐색하는 방법이므로 그래프 알고리즘을 적용해볼 수 있을 것 같다는 느낌은 들지만, 이 문제의 경우 오른쪽 또는 아래로 선택하여 이동 + 이 과정을 최악의 경우 2n-1번 반복하여 얻는 결과를 보여줘야 한다. 이 때, 시간복잡도를 보면 2^(2n-1)이 될 것이므로 n이 최대 100이니 2^199 만큼의 연산을 수행해야 완전탐색으로 최대값을 알아낼 수 있다. 2^10이 1,000이라고 할 때,  보통100,000,000(1억)번의 연산을 할 때의 시간을 1초로 가정하므로 2^199는 터무니없이 많은 연산량을 필요로 하고 있음을 알 수 있다. 따라서 완전탐색으로는 접근할 수 없다.

 

2. 그리디로 접근했을 때 가능한가?

-> 항상 그 다음 수를 고를 때, 다음 수가 크다고 해서 최종 합이 항상 최대가 되는 건 아니므로 그리디로는 접근이 어렵다.

 

3. 동적계획법으로 접근했을 때 가능한가?

-> 큰 문제를 작은 문제로 쪼개는 방식으로 접근해볼 수 있다. dp[i][j] = Math.max(dp[i-1][j] + arr[i][j], dp[i][j-1] + arr[i][j]) 로 점화식을 세우면 DP로 접근할 수 있으며, 이는 최대 2중 반복문 정도를 이용할 뿐이므로 시간복잡도도 n^2에 그친다. n이 최대 100이므로 동적계획법을 사용하면 문제를 풀 수 있을 것이다.

 

문제 풀이

package 코드트리.DP;

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

public class 정수_사각형_최대_합 {
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // init dp
        int[][] dp = new int[n+1][n+1];
        dp[1][1] = arr[1][1];
        for (int i = 2; i <= n; i++) {
            dp[1][i] = dp[1][i - 1] + arr[1][i];
        }
        for (int i = 2; i <= n; i++) {
            dp[i][1] = dp[i-1][1] + arr[i][1];
        }

        // tabulation operation
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = Math.max(dp[i][j - 1] + arr[i][j], dp[i - 1][j] + arr[i][j]);
            }
        }

        System.out.println(dp[n][n]);
    }
}