백준 11660: 구간합 구하기 5

 

📃 문제: 백준 11659(구간합 구하기 5)

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이다.

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

 

 

 

🥈 난이도: 실버 1

 

 

 

😲 사용한 개념: 구간합

S[i] = S[i-1] + A[i]

 

구간합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n) -> O(1)로 감소한다.

 

 

 

📖 풀이 사고 과정

 

 

 

 

 

👩‍💻 구현 코드(c++ 사용)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int D[1025][1025];
int A[1025][1025];
int main(void) {
    int result[100000], x1, x2, y1, y2;
    int N, M;
    //N*N 배열 입력받기
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    //구간합 구하기
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            D[i][j] = D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1] + A[i][j];
        }
    }
    //(x1,y1,x2,y2) 범위 구하기
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        result[i] = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
    }
    for (int i = 0; i < M; i++) {
        printf("%d\n", result[i]);
    }
    return 0;
}