[BOJ] 11660 구간 합 구하기

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

이 문제를 풀기 위해서는 dp[i][j]가 1,1부터 i,j까지 영역의 합을 나타내야 한다.

input

위와 같은 값이 주어졌다고 가정해보자.

dp[i][j]

배열의 각 칸에는 1,1부터 i,j까지의 영역의 합을 입력해야 한다.

?에는 1+2+5+7, 즉 15가 와야 한다.

파란 영역(1+5)과 빨간 영역(1+2)을 활용하여 ? 값을 구하기 위해서는 중복되는 부분(1)을 빼줘야 한다.

점화식을 세우면 dp[i][j]=input[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] 이란 것을 직관적으로 알 수 있다.

 

이제 dp 배열을 활용하여 답을 구하면 된다.

초록색 영역의 합을 구해야 된다고 가정하자.

초록색 영역=빨강색 영역-주황색 영역-노란색 영역+파란생 영역으로 나타낼 수 있다.

따라서 x1, y1, x2, y2가 주어졌을 때, (y1,x1)->(y2,x2) 영역을 합은

dp[y2][x2]=dp[y1-1][x2]-dp[y2][x1-1]+dp[y1-1][x1-1] 이라는 것을 알 수 있다.

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define endl '\n'
#define ll long long

using namespace std;

int dp[1025][1025];
int N,M;

void input() {
    cin>>N>>M;
    int num;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> num;
            dp[i+1][j+1] =dp[i][j+1]+dp[i+1][j]-dp[i][j]+num;
        }
    }
}

void init() {
}


void solution() {
       for (int i = 0; i < M; i++) {
           int x1, y1, x2, y2;
           cin >>y1>>x1>>y2>>x2;
           cout <<dp[y2][x2]-dp[y1-1][x2]-dp[y2][x1-1]+dp[y1-1][x1-1]<<endl;

       }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();

    return 0;
}