[백준/JAVA] 1749번: 점수따먹기

🔺 문제

1749번: 점수따먹기

 

🧩  해결 아이디어

• 브루트포스, 2차원 누적합

1. dp 배열을 채운다.

dp 배열의 왼쪽 값 + dp 배열의 위쪽 값 - 2번 받아 중복되는 dp 배열의 왼쪽 위 대각선 값 + map 배열의 현재 위치 값

 

2. dp 배열을 돌며 최댓값을 구한다.

 

 

💥 유의사항

최댓값 비교 할 때, long형으로 받고 비교해야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] map, dp;
    
    static long max = Integer.MIN_VALUE;    // long !!
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N + 1][M + 1];
        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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        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] + map[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++) {
                        long result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
                        max = Math.max(max, result);
                    }
                }
            }
        }
        
        System.out.println(max);
    }
}
 

 

 

---

💬 느낀 점

2차원 누적합에 익숙해집시다....

예~~~전에 풀었던.. 잊고 있던 백준 구간 합 구하기 5 문제가 생각났다. 

[백준/JAVA] 11660번: 구간 합 구하기 5

 

1회독	2회독	3회독	4회독	5회독
12.1

---

(참고)

✔ 풀이 참고

[ BOJ ][JAVA][1749] 점수따먹기

[백준 1912, 1749번] 연속합, 점수따먹기

 

 

✔  그림 복습용 (구하는 영역)

[백준]1749 점수따먹기

백준 1749 점수따먹기 Kotlin (2차원 누적 합)