[백준/JAVA] 20002번: 사과나무

🔺 문제

20002번: 사과나무

 

 

🧩  해결 아이디어

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

 

지난 주에 풀었던 문제가 생각났다.

그런데 이제 거기에 정사각형 조건만 추가된 버전!

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

 

1. 2차원 배열에 대한 2차원 누적합 배열을 구한다.

2. 2차원 누적합 배열을 돌며 정사각형 부분행렬을 구하고 이 중 최댓값을 구한다.

 

 

 

💥 유의사항

4중 for문 시 인덱스 주의

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long max = Integer.MIN_VALUE;
    
    static int N;
    static int[][] board, dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        board = new int[N + 1][N + 1];
        dp = new int[N + 1][N + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= N ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 2차원 배열에 대한 누적합
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i][j];
            }
        }
        
        // 부분행렬 구하기
        for(int x1 = 1 ; x1 <= N ; x1++) {
            for(int y1 = 1 ; y1 <= N ; y1++) {
                for(int x2 = x1 ; x2 <= N ; x2++) {
                    for(int y2 = y1 ; y2 <= N ; y2++) {
                        // 정사각형이 아니면 pass
                        if(x2 - x1 != y2 - y1)  continue;
                        
                        long ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
                        max = Math.max(max, ans);
                    }
                }
            }
        }
        
        System.out.println(max);
    }
}
 

 

 

---

🔺 다른 풀이들

- 정사각형 처리를 이렇게 3중 for문으로 끝내신 분들도 많았다.

for(int k = 1; k <= n; k++) {
    for (int i = k; i <= n; i++) {
        for (int j = k; j <= n; j++) {
            int temp = pre[i][j] - pre[i-k][j] - pre[i][j-k] + pre[i-k][j-k];
            max = Math.max(max, temp);
        }
    }
}

---

💬 느낀 점

2차원 누적합 이제 좀 이해를 했다!!

누적합 문제 굿!!

 

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

---

(참고)

✔ 2차원 누적합 배열 활용 유사문제

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

20058번: 마법사 상어와 파이어스톰

 

- 2차원 누적합 관련 그림 설명 굿!

[Prefix Sum] BOJ 20002 사과나무