C++:: 프로그래머스 < 파괴되지 않은 건물 >

누적합을 사용하여야 효율성 테스트를 통과할 수 있는 문제이다.

누적합에 대한 간단한 예시를 보여주자면
n = 4, m = 5인 배열에서 (0, 0) 부터 (2,3)까지 3을 더하고 싶다 가정해보자.

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

초기 0으로 값이 된곳에서 r1,c1(0, 0) , r2,c2(2,3) 에 3을 더할 것인데
먼저 r1,c1 과 r2+1, c2+1 좌표에는 값을 그대로 넣어준다.

3 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 3

이후 r1,c2+1 와 r2+1,c1 에는 -1을 곱해준 값을 더해준다.

3 0 0 0 -3
0 0 0 0 0
0 0 0 0 0
-3 0 0 0 3

이후 수평과 수직에 대해 이중 for문을 돌면서 값을 더해나가면 된다.

수평 먼저한 결과
3 3 3 3 0
0 0 0 0 0
0 0 0 0 0
-3 -3 -3 -3 0
0 0 0 0 0

수직까지하면
3 3 3 3 0
3 3 3 3 0
3 3 3 3 0
0 0 0 0 0

#include <string>
#include <vector>
using namespace std;

int cusum[1001][1001];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int n = board.size(), m = board[0].size();
    
    for(auto sk: skill) {
        int degree = sk[5];
        if(sk[0] == 1) degree = -degree;
        cusum[sk[1]][sk[2]] += degree;
        cusum[sk[3]+1][sk[4]+1] += degree;
        cusum[sk[1]][sk[4]+1] -= degree;
        cusum[sk[3]+1][sk[2]] -= degree;
    }
    
    for(int i=0; i<n; i++) { // 왼쪽에서 오른쪽 누적합
        for(int j=0; j<m; j++) {
            cusum[i][j+1] += cusum[i][j];
        }
    }
    
    for(int j=0; j<m; j++) { // 위에서 아래 누적합
        for(int i=0; i<n; i++) {
            cusum[i+1][j] += cusum[i][j];
        }
    }
    
    int answer = 0;
    for(int i=0; i<n; ++i) { // 누적합 배열과 board 합쳐 결과 계산
        for(int j=0; j<m; ++j) {
            if(board[i][j] + cusum[i][j] > 0) answer++;
        }
    }
    
    return answer;
}