[백준/JAVA] 2167번: 2차원 배열의 합

📖 문제

2167번: 2차원 배열의 합

 

 

💡  풀이 방식

• (i,j) ~ (x,y) 구간에 대한 누적합을 구한다.

1) 초기 2차원 누적합 행렬은 다음과 같이 채운다.

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

 

2) 부분 행렬의 값은 다음과 같이 구한다.

dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1]

 

 

 

 

💥 유의사항

dp[N][M]으로 해서 풀면 ArrayIndexOutOfError가 뜨는 경우가 있으니

안전하게 크기는 [N + 1][M + 1]로 해서 좌표를 (1,1)부터 시작하도록 하자,,

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K;
    static int[][] arr, dp;
    
    static StringBuilder sb = new StringBuilder();
    
    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());
        
        arr = new int[N + 1][M + 1];
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                arr[i][j + 1] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp = new int[N + 1][M + 1];
 
        // 2차원 누적합 dp 배열 채우기
        dp[1][1] = arr[1][1];
        for(int i = 2 ; i <= N ; i++) dp[i][1] = dp[i-1][1] + arr[i][1];    // 맨 왼쪽 줄
        for(int j = 2 ; j <= M ; j++) dp[1][j] = dp[1][j - 1] + arr[1][j];    // 맨 윗 줄
        
        for(int i = 2 ; i <= N ; i++) {
            for(int j = 2 ; j <= M ; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];
            }
        }
        
        K = Integer.parseInt(br.readLine());
        while(K --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            if(i == x && j == y)    // 두 좌표가 같다면, 계산할 필요 없이 
                sb.append(arr[i][j] + "\n");
            else
                sb.append(dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1] + "\n");
        }
        
        System.out.println(sb);
    }
}
 

 

 

---

💦 어려웠던 점

40분 소요,,

오랜만에 2차원 누적합 풀려니 시간이 좀 더 걸렸다..

 

더 집중해서 빠르게 생각해내서 풀자구나,,,

 

 

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

---

(참고)

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