[백준/Java] 11660번 - 구간 합 구하기 5

문제

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

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

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

여기서 (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)

출력

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

 

 

- 문제 풀이 방식

1. BufferedReader, StringTokenizer을 통해 n, m을 입력받는다. 

 

2. 반복문을 통해 2차원 배열 A를 입력받으면서 구간 합 배열 S를 계산하여 저장한다. 

    구간 합을 구할 때는 이전 구간 합과 현재 배열 값을 더해 계산한다. 

     -> S[ i ] = S[ i - 1 ] + A[ i ], 2차원 배열에서는 S[ i ][ j ] = S[ i ] [ j - 1 ]

   

   * 이때 고려할 점 2가지가 있다. 

     1) i, j가 모두 1인 경우

        : 2차원 배열의 첫번째 값을 의미한다. 이때는 이전 구간 합이 없으므로 S[ i ][ j ] = A[ i ][ j ] 이다. 

     2) j만 1인 경우 

        : 4x4 배열에서(n = 4) 구간 합 S[3][1]을 구하는 경우, 구간 합을 구하면 S[2][4] + A[3][1]이다. 

         즉, S[ i ][1]의 구간 합을 구하는 식은 S[ i - 1][n] + A[ i ][ j ] 이다. 

 

3. m개의 시작, 종료 i, j를 입력받아 해당 구간 합을 계산한다. 

   주의할 점은 그냥 S[종료i][종료j] - S[시작i][시작j-1]로 계산하면 안 된다. 

 

    1) i, j가 1이 아닌 경우

       : (2,3) ~ (3,4)의 구간의 영역은 다음과 같다. ((3,1)과 (3,2)가 포함되지 않는다.)

         -> 포함되지 않는 부분을 제외하려고 한 줄 씩 계산했다.

           반복문을 통해 시작 i부터 종료 i까지(k라고 둠) m 크기의 결과 배열을 만들어 구간 합을 매번 더해준다. 

            S[2][4] - S[2][2]

            S[3][4] - S[3][2]

        => S[ k ][종료j] - S[ k ][시작i - 1]

 

    2) 시작 i, j가 모두 1인 경우

       : (1,1) ~ (3,4)의 구간 합 영역은 다음과 같다. 

           시작 j가 1인 경우, 빼야 하는 누적 합 배열이 이전 i 배열의 마지막 값이 된다. 

            S[2][4] - S[1][4]

            S[3][4] - S[2][4]

        => S[ k ][종료j] - S[ k-1 ][ n ]

 

 

           시작 i와 j가 모두 1인 경우, S[1][4]이므로, 아무 값도 빼지 않아도 된다. 
            S[1][4]

        => S[ k ][종료j]

 

 

- 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		int m = Integer.parseInt(st.nextToken());
		int[][] A = new int[n+1][n+1];
		int[][] S = 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++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				if (j == 1) {
					if (i == 1) {
						S[i][j] = A[i][j];
					}
					else {
						S[i][j] = S[i-1][n] + A[i][j];
					}
				}
				else {
					S[i][j] = S[i][j-1] + A[i][j]; 
				}
			}
		}

		int startI, startJ;
		int endI, endJ;
		int[] result = new int[m+1];
		
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			startI = Integer.parseInt(st.nextToken());
			startJ = Integer.parseInt(st.nextToken());
			endI = Integer.parseInt(st.nextToken());
			endJ = Integer.parseInt(st.nextToken());
			
			for (int k = startI; k <= endI; k++) {
				if (startJ == 1) {
					if (k == 1) {
						result[i] += S[k][endJ];
					}
					else {
						result[i] += S[k][endJ] - S[k-1][n];
					}
				}
				else {
					result[i] += S[k][endJ] - S[k][startJ-1];
				}

			}
		}

		for (int i = 1; i <= m; i++) {
			System.out.println(result[i]);
		}
		
		br.close();
	}

}

 

 

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

11660번: 구간 합 구하기 5