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

문제 해석

• 첫번째 입력 값으로는 행렬(NxN)인 N값과 구해야하는 횟수 M이 주어진다.

• 두번째 줄 부터는 행렬(NxN)에 들어갈 숫자를 차례대로 입력받는다.

• 행렬에 들어갈 숫자를 모두 입력받았다면, 그 다음줄 부터는 (x1, y1), (x2, y2)의 값을 M개 만큼 입력받는다.

• 문제 로직에 대한 정리에 앞서 문제 설명을 보면 M이 1 이상 100,000이하라고 한다. 즉 질의가 최대 100,000개라는 것인데 이런 경우 질의를 받을 때마다 계산을 하게 되면 시간복잡도가 O(NM)이 나오게 된다. 하지만, 이 문제는 시간 제한을 1초로 걸어놓았기 때문에 계산을 미리 해두고 결과값을 뽑아내는 방식으로 가야한다.

• 문제의 절차 로직을 정리하면 아래와 같다.
  

• 누적합을 활용하여 해당 질의를 구하는 식은 아래와 같이 표현할 수 있다.

sum(x2, y2) - sum(x1-1)(y2) - sum(x2)(y1-1) + sum(x1-1)(y1-1) 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //행렬(NxN)
        int M = Integer.parseInt(st.nextToken()); //질의 수

        int[][] sum = 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++){
                sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        int answer = 0; //답을 담는 변수

        //구간 합 구한 후 질의 계산
        for(int i = 0; i < M; i++){ //잘의 개수만큼
            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());
            answer = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
            System.out.println(answer);
        }
    }

}

결과

느낀 점

생각보다 이해하면 간단한 문제였지만 처음에 생각해내기가 좀 어려웠던 문제였다, 그래도 이번 문제를 기회로 누적합이 점점 익숙해져가는 느낌이 든다!