[11660] 구간 합 구하기 5

✔ 구간 합 구하기 5

[백준 11660]

문제 분석하기

질의의 개수가 100000이므로 구간 합 배열을 이용해야 함

구간 합 배열이 1차원에서 2차원으로 확장되었으므로 새로 정의가 필요

D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합

손으로 풀어보기

1. 2차원 구간 합 배열의 1행, 1열부터 구함
   • D[1][j] = D[1][j - 1] + A[1][j]
   • D[i][1] = D[i - 1][1] + A[i][1]
2. 1행, 1열을 통해 나머지 2차원 구간 합 배열을 채움
   • D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]
3. 구간 합 배열을 통해 질의에 대한 답을 구함
   • X1, Y1, X2, Y2에 대한 답 = D[X2][Y2] - D[X1 - 1][Y2] - D[X2][Y1 - 1] + D[X1 - 1][Y1 - 1]

합 배열 채우기

질의 답 구하기

슈도코드 작성하기

N(배열 크기) M(질의 수) 저장하기
for(N만큼 반복하기) {
    for(N만큼 반복하기) {
        원본 배열 저장하기
    }
}
for(N만큼 반복하기) {
    for(N만큼 반복하기) {
        합 배열 저장하기
        D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
    }
}
for(M만큼 반복하기) {
    질의 계산 및 출력하기
    결과 = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
}

코드 구현하기

/**
 * 11660) 구간_합_구하기_5
 */
public class D004_11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N(배열 크기) M(질의 수) 저장하기
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        // 원본 배열 저장하기
        int A[][] = 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());
            }
        }
        // 합 배열 저장하기
        int D[][] = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[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());
            int result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
            System.out.println(result);
        }
    }
}