[JAVA] 백준 (실버1) 11660번 구간 합 구하기 5

링크

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

---

문제 설명

정답률 44.026%
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
• 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.
• 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다.
• 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

---

출력 예제

• 총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

27
6
64

---

풀이

구간 합 구하기 4를 2차원 배열로 응용한 문제이다. 이 문제 역시 구간 합을 이용하여 풀이하여야 하고 일일이 배열에서 찾아 값을 더할 경우 시간초과가 난다.

구간 합 배열은 다음과 같이 행과 열에서 각각 1씩 뺀 구간 합을 더하고 중복된 부분의 구간 합을 뺀 뒤 원래 원소의 값을 더하면 된다.

int[][] sum = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + numbers[i][j];
    }
}

그림으로 보면 (3, 2)의 구간 합을 구하면 다음과 같다.

이제 문제의 요구사항대로 예제를 (2, 2)에서 (3, 4)까지의 구간 합을 구해본다.

이를 일반화하면 다음과 같다.

result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());  //수의 개수
        int M = Integer.parseInt(st.nextToken());  //합의 개수

        //입력값 배열
        int[][] numbers = 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++) {
                numbers[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //구간 합 배열
        int[][] sum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + numbers[i][j];
            }
        }

        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());
			//(x1, y1)부터 (x2, y2)까지의 구간 합
            System.out.println(
                    sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]
            );
        }
    }
}