[코드트리/INTERMEIDATE LOW] 정수 사각형 최대 합 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX_N = 1_000_000;
    static int N;
    static int[][] arr;
    static long[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1][N + 1];       
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        dp = new long[N + 1][N + 1];
        initialize();
 
        // 왼쪽과 위쪽에서 온 값 中 큰 값 가져오기
        for(int i = 1 ; i < N ; i++) {
            for(int j = 1 ; j < N ; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
 
        System.out.println(dp[N - 1][N - 1]);
    }
 
    // 초기화 함수 : 0번째 행과 열 미리 채우기
    private static void initialize() {
        dp[0][0] = arr[0][0];
 
        for(int i = 1 ; i < N ; i++) {
            dp[0][i] = dp[0][i - 1] + arr[0][i];
            dp[i][0] = dp[i - 1][0] + arr[i][0];
        }
    }
}

 

 

 

🧩  해결 아이디어

• DP - 격자 안에서 한 칸씩 전진

- 값을 입력받는 2차원 배열과, 최댓값을 저장하는 경로 저장용 2차원 배열 DP를 생성한다.

- 경로 저장용 배열의 0번째 행과 0번째 열은 기존 값에 현재값을 더하면 되므로 미리 초기화해둔다.

private static void initialize() {
    dp[0][0] = arr[0][0];

    for(int i = 1 ; i < N ; i++) {
        dp[0][i] = dp[0][i - 1] + arr[0][i];
        dp[i][0] = dp[i - 1][0] + arr[i][0];
    }
}

 

- 초기화 시켜둔 DP 배열에서 (1,1)번째부터 왼쪽과 위쪽에서 온 값 中 큰 값과 현재 칸의 값을 더해 저장한다.

for(int i = 1 ; i < N ; i++) {
    for(int j = 1 ; j < N ; j++) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
    }
}

 

 

 

 

 

---

💬 느낀 점

이런 규칙이 단순한 dp라면 언제든지 환영입니다..

 

1회독	2회독	3회독	4회독	5회독
V