[백준-자바] 11660번 구간 합 구하기 5 / 2022.05.21

 

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

11660번: 구간 합 구하기 5

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader((new InputStreamReader(System.in)));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken()); // 표의 크기 NxN
        int M = Integer.parseInt(stringTokenizer.nextToken()); // 합을 구해야 하는 횟수 M

        int [][] number = new int [N+1][N+1]; // 표 입력
        for(int i=1; i<N+1; i++){ // 행
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=1; j<N+1; j++){ // 열
                number[i][j] = Integer.parseInt(stringTokenizer.nextToken());
           }
        }

        int [][] newNum = new int [N+1][N+1]; // 구간 합 표 구하기
        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                newNum[i][j] = newNum[i][j-1] + newNum[i-1][j] - newNum[i-1][j-1]
                        +number[i][j];
            }
        }

        for(int i=0; i<M; i++){ // 범위의 합 구하기
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x1 = Integer.parseInt(stringTokenizer.nextToken());
            int y1 = Integer.parseInt(stringTokenizer.nextToken());
            int x2 = Integer.parseInt(stringTokenizer.nextToken());
            int y2 = Integer.parseInt(stringTokenizer.nextToken());
            int result = newNum[x2][y2] - newNum[x1-1][y2] - newNum[x2][y1-1]
                    + newNum[x1-1][y1-1];
            System.out.println(result);
        }
    }
}

 

풀이 : 

1. 배열 입력 받기

2. 구간 합 배열 구하기

3. 문제에서 원하는 범위의 합 구하기

 

* 구간 합 배열 구하기 

 

* 문제에서 원하는 범위의 합 구하기