[백준/C++] 11660 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

문제분석

1. 분류
   • 구간합(Prefix sum)
   • 다이나믹 프로그래밍(Dynamic Programming)
2. 문제설명
   • 배열의 크기 N 입력
   • 구간합 구하는 횟수 M 입력
   • 배열 입력, 구간합 좌표 입력
   • 입력된 좌표 (시작X, 시작Y) (종료X, 종료Y) 사이의 구간을 입력
   • 구간합 -> O(N)의 속도로 문제 도출

입력

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

출력

27
6
64

코드

#include <iostream>
using namespace std;

int arr[1026][1026];
int N, M;
int value[1026][1026];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> arr[y][x];
            value[y][x] += (arr[y][x] - value[y - 1][x - 1] + value[y][x - 1] + value[y - 1][x]);
        }
    }

    for (int t = 0; t < M; t++) {
        int stX, stY, edX, edY;
        cin >> stX >> stY >> edX >> edY;
        int sum = value[edX][edY];
        sum -= (value[stX - 1][edY] + value[edX][stY - 1]);
        sum += value[stX - 1][stY - 1];
        cout << sum << "\n";
    }
}

 

문제풀이

1. 지점의 합 = 이전 행의 합 + 이전 열의 합 -> 중복 부분 제거: 이전 행의 총 합 + 이전 열의 총 합 - 이전 열의 총 합 - 이전 행,열의 총 합
2. 좌표지점의 총 합 계산하기 -> sum = value[x2][y2] - value[x1-1][y2] - value[x2][y1-1] + value[x1-1][y1-1];
3. 중복 부분을 제거하는 포인트를 기억한다면, 어렵지 않게 구현할 수 있다.