백준 11660번 구간 합 구하기 5

문제 링크입니다: https://www.acmicpc.net/problem/11660

 

백준 11659번 구간 합 구하기 4(https://jaimemin.tistory.com/1143)의 이차원 버전이었습니다.

 

그림을 그리고 색칠해나가보면 이해가 쉽게 될 것입니다!

시작부터 끝까지의 부분합을 구하기 위해 우선 (끝y, 끝x)까지의 부분합을 더하고 (시작y - 1, 끝x)과 (끝 y, 시작x - 1)을 빼줍니다. 

그런데 이 때, 두 값을 뺀 부분의 교집합이 있으므로 해당 부분은 다시 더해줍니다.

 

 

#include <iostream>

using namespace std;

 

const int MAX = 1024 + 1;

 

int pSum[MAX][MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        for(int i=0; i<N; i++)

                 for (int j = 0; j < N; j++)

                 {

                         int num;

                         cin >> num;

 

                         //겹치는 pSum[i][j] 빼주는게 중요

                         pSum[i + 1][j + 1] = pSum[i + 1][j] + pSum[i][j + 1] - pSum[i][j] + num;

                 }

 

        for (int i = 0; i < M; i++)

        {

                 int y, x, y2, x2;

                 cin >> y >> x >> y2 >> x2;

 

                 cout << pSum[y2][x2] - pSum[y - 1][x2] - pSum[y2][x - 1] + pSum[y - 1][x - 1] << "\n";

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

 

 

 

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~