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

📖 문제

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

 

 

 

💡  풀이 방식

• DP

1. 2차원 배열 값을 입력받는다.

2. DP배열을 초기화한다.

  - 맨 윗 줄         : 오른쪽에서 온 값을 누적해 더한 값으로 변경한다.

  - 맨 오른쪽 줄 : 위쪽에서 내려온 값을 누적해 더한 값으로 변경한다.

 

3. 초기화한 값을 활용해 dp 배열을 채운다.

 - 위쪽과 오른쪽에서 온 값 中 더 작은 값을 선택하고 현재 칸의 값에 누적해 더한다.

 

4. 맨 왼쪽 아래에 있는 값을 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
 
        dp = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 위쪽 줄 채우기
        for(int i = N - 2 ; i >= 0 ; i--) {
            dp[0][i] += dp[0][i + 1];
        }
 
        // 오른쪽 줄 채우기
        for(int i = 1 ; i < N ; i++) {
            dp[i][N - 1] += dp[i - 1][N - 1];
        }       
 
        // DP 배열 채우기
        for(int i = 1 ; i < N ; i++) {
            for(int j = N - 2 ; j >= 0 ; j--) {
                dp[i][j] += Math.min(dp[i - 1][j], dp[i][j + 1]);    // 위쪽과 오른쪽 중 작은 값 선택해 
            }
        }
 
        System.out.println(dp[N - 1][0]);
    }
}

 

 

 

---

 

 

 

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