[누적합] 1749번 - 점수따먹기

[백준] 1749번 - 점수따먹기

📝 나의 풀이

풀이 순서

1. 입력값으로 누적합 구하기
2. 합이 최대가 되는 부분행렬 구하기 → 완전 탐색

2차원 배열에서 모든 가능한 부분 배열의 합을 계산해서 최대 합을 구해야 하기 때문에
(x1, y1)에서 (x2, y2)까지의 부분 배열의 합을 계산하는 반복문을 작성해야 한다.

[알고리즘] 누적합(prefix sum)
2차원 배열의 누적합 구하는 방법은 위 글을 참고하면 된다.

그리고 주의해야 할 점은
입력 값에 양수 뿐만 아니라 음수도 주어지기 때문에
최대값을 구하기 위한 변수 maxScore의 값을 "0"으로 초기화하는 멍청한 실수를 하면 안된다.
난 0으로 초기화해서 계속 틀렸었다....

👩🏻‍💻 최종 코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] sum = new int[N+1][M+1];
		int[][] ground = new int[N+1][M+1];
		int maxScore = Integer.MIN_VALUE;

		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= M; j++) {
				ground[i][j] = Integer.parseInt(st.nextToken());
				sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + ground[i][j];
				maxScore = Math.max(maxScore, sum[i][j]);
			}
		}
		
		
		for(int x1 = 1; x1 <= N; x1++) {
			for(int y1 = 1; y1 < M; y1++) {
				for(int x2 = x1; x2 <= N; x2++) {
					for(int y2 = y1; y2 <= M; y2++) {
						int tmp = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
						maxScore = Math.max(maxScore, tmp);
					}
				}
			}
		}
		
		System.out.println(maxScore);

	}

}