[백준]11660. 구간 합 구하기 5(Java, 자바)

문제

11660. 구간 합 구하기 5

📌 아이디어

누적합을 통해 문제를 해결했습니다.

2차원 배열의 각 행을 기준으로 누적합을 저장했습니다.

for (int i = 1; i<=n; i++) {
	st = new StringTokenizer(br.readLine(), " ");
    for (int j = 1; j<=n; j++) {
    	prefixSum[i][j] = prefixSum[i][j-1] + Integer.parseInt(st.nextToken());
    }
}

그리고 input data에서 주어진 구간을 활용해 정답을 도출했습니다.

for (int j = x1; j<=x2; j++) {
	sum = sum + (prefixSum[j][y2] - prefixSum[j][y1-1]);
}

📌 코드

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


class BOJ_11660 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] prefixSum = new int[n+1][n+1];
		
        // 2차원 배열 누적합
        for (int i = 1; i<=n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j<=n; j++) {
                prefixSum[i][j] = prefixSum[i][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i<m; i++) {
            int sum = 0;
            st = new StringTokenizer(br.readLine(), " ");
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            // 구간합 도출
            for (int j = x1; j<=x2; j++) {
                sum = sum + (prefixSum[j][y2] - prefixSum[j][y1-1]);
            }
            sb.append(sum + "\n");
        }
        System.out.println(sb);
    }
}

피드백 및 개선점은 댓글을 통해 알려주세요😊