[Java] 백준 1729번 점수따먹기

문제

https://www.acmicpc.net/problem/1749

 

코드

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String args[]) throws Exception{
      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[][] nums = new int[n + 1][m + 1];
      int[][] dp = new int[n + 1][m + 1];
      for(int i = 1; i <= n; i++) {
          st = new StringTokenizer(br.readLine());
          for(int j = 1; j <= m; j++) {
              nums[i][j] = Integer.parseInt(st.nextToken());
              dp[i][j] = nums[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
          }
      }
      
      int max = Integer.MIN_VALUE;
      
      for(int i = 1; i <= n; i++) {
          for(int j = 1; j <= m; j++) {
              for(int x = 0; x < i; x++) {
                  for(int y = 0; y < j; y++){
                      max = Math.max(max,
                      dp[i][j] - dp[x][j] - dp[i][y] + dp[x][y]);
                  }
                }
          }
      }
      
      System.out.println(max);
  }
}

 

풀이

누적합을 이용한 DP문제였다. 단순한 누적합을 구하는데까지는 했는데 일부분의 합을 누적합을 사용해서 구하는 것이 헷갈려서 고생을 좀 했기에 과정을 정리했다.

예를 들어 이 빨간 부분의 누적합을 구하고 싶다면?

초록색 부분의  누적합과 파란색 부분의 누적합에서 겹치는 부분을 빼주는 방법으로 구하는것 까지는 쉽다.

식으로 정리하면

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

 

그렇다면 다음과 같은 경우에는 어떻게 누적합을 이용해서 합을 구할 수 있을까?

[1][2]부분의 누적합에서 초록색과 파란색으로 표시한 숫자 부분의 누적합을 빼면 구할 수 있다.

그러나 이 경우 그림으로 확인할 수 있듯이 겹쳐지는 부분이 존재한다.

겹쳐지는 부분은 두번 제외가 됐으므로 다시 더하면 되고

이를 식으로 나타내면

dp[i][j] - dp[x][j] - dp[i][y] + dp[x][y]; 와 같이 표현할 수 있다.

여기서 x와 y는 내가 확인하고자 하는 범위보다 1작은 수가 된다고 할 수 있을듯?)