[c++][프로그래머스] 파괴되지 않은 건물

프로그래머스 파괴되지 않은 건물 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92344

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

문제 설명

• 이 문제는 정확성과 효율성 테스트가 각각 점수가 있는 문제입니다.
• 정확성 테스트를 해결하기 위해서는 아주 간단하게 스킬 별로 좌표에 맞춰 board 에 degree를 더해주거나 빼주기만 하면 됩니다. 하지만 이 경우에 시간 복잡도가 O(N*M*K)가 되어 효율성 테스트를 통과할 수 없습니다. 
• 효율성 테스트를 통과하기 위해서는 2차원 누적합의 개념을 도입해야 합니다.
• 누적합의 개념과 문제 풀이에 대해 카카오 테크 블로그에 아주 자세하게 설명되어 있어서 블로그를 참고하시면 문제를 이해하시는데 어려움이 없을 것 같습니다!

코드

#include <string>
#include <vector>

using namespace std;

int cusum[1010][1010];
int N, M;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    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+1; ++i) { // 왼쪽에서 오른쪽 누적합
        for(int j=0; j<M; ++j) {
            cusum[i][j+1] += cusum[i][j];
        }
    }
        
    for(int j=0; j<M+1; ++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;
}

실행 결과