2022 KAKAO BLIND RECRUITMENT / 파괴되지 않은 건물

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int N = board.size(), M = board[0].size();
    int n = skill.size(), m = skill[0].size();
    
    vector<vector<int>> skill_sum(N + 1, vector<int>(M + 1, 0));
    for (int i = 0; i < n; ++i) {
        if (skill[i][5] == 0) continue;
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int val = (skill[i][0] == 1 ? -1 : 1) * skill[i][5];
        
        skill_sum[r1][c1] += val;
        skill_sum[r2 + 1][c2 + 1] += val;
        skill_sum[r1][c2 + 1] += -val;
        skill_sum[r2 + 1][c1] += -val;
    }
    
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j < M; ++j) {
            skill_sum[i][j] += skill_sum[i][j - 1];
        }
    }
    
    for (int i = 0; i < M; ++i) {
        for (int j = 1; j < N; ++j) {
            skill_sum[j][i] += skill_sum[j - 1][i];
        }
    }
    
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            ans += (board[i][j] + skill_sum[i][j]) > 0;
        }
    }
    
    return ans;
}

2차원 행렬에 대한 누적합 prefix sum

[(0, 0), (1, 1)] 구간에 대해 변화량 n 적용 시, 꼭짓점만 고려하기 때문에 상수시간내에 처리가능하다.

2 0 -2

0 0 0

-2 0 2