[프로그래머스][level3] 파괴되지 않은 건물 (C++)

https://programmers.co.kr/learn/courses/30/lessons/92344

코딩테스트 연습 - 파괴되지 않은 건물

 

 

[난이도] level3
[유형] 누적합

[풀이]
공식풀이 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

 

#include <string>
#include <vector>
using namespace std;
int sum[1002][1002],N,M;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    N=board.size();
    M=board[0].size();
    for(auto s : skill){
        int d=s[5];
        if(s[0]==1) d*=-1;
        sum[s[1]][s[2]]+=d;
        sum[s[3]+1][s[2]]+=-d;
        sum[s[1]][s[4]+1]+=-d;
        sum[s[3]+1][s[4]+1]+=d;
    }
    for(int i=0;i<N;i++)
        for(int j=1;j<M;j++) sum[i][j]+=sum[i][j-1];

    for(int i=0;i<M;i++)
        for(int j=1;j<N;j++) sum[j][i]+=sum[j-1][i];

    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(board[i][j]+sum[i][j]>0) answer++;

    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/파괴되지_않은_건물.cpp