[BJ]_점수따먹기

정리

n = 3, m= 6
초기 dp 입력 값

0	0	0	0	0	0	0
0	-3	2	1	-3	4	0
0	2	-2	-1	4	2	5
0	3	3	-2	3	0	2

---

dp
각 위치별 행렬의 최대값을 구하는 것. (누적합)

0	0	0	0	0	0	0
0	-3	-1	0	-3	1	1
0	-1	-1	-1	0	6	11
0	2	5	3	7	13	20

dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

예시

• dp[2][5] 2는 아직 갱신 안된 값임.

dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
↓
2 += 1 + 0 - (-3) → 6

 

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

//        BufferedReader br = new BufferedReader(new FileReader("test.txt")); // 입력 파일 열기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken())+1; // 행의 수
        int M = Integer.parseInt(st.nextToken())+1; // 열의 수

//        int[][] graph = new int[N][M]; // 그래프 배열 초기화
        int[][] dp = new int[N][M];

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < M; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // dp 초기값 채우기.
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                // 현재 위치까지 행렬 최대값 구하기
                // 바로 위까지 행렬의 최대값 + 바로 옆까지 행렬 최대값 - 중복된 행렬의 최대값
                dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int si = 1; si < N; si++) {
            for (int sj = 1; sj < M; sj++) {
                for (int i = si; i < N; i++) {
                    for (int j = sj; j < M; j++) {
                        // 부분합 중 최대 구하기.
                        // 범위내 오른쪽 가장 아래(현재) - 시작점 위 - 시작점 왼쪽 + 시작점 왼위(중복으로 지워진값)
                        int tmp = dp[i][j] - dp[si-1][j] - dp[i][sj-1]+dp[si-1][sj-1];
                        ans = Math.max(tmp,ans);
                    }
                }
            }
        }
        System.out.println(ans);
    }
}