[C++]프로그래머스 : 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물

먼저 누적합에 대한 개념은 여기에 정리해뒀다
:https://velog.io/@bjy6631/%EB%88%84%EC%A0%81%ED%95%A9-Prefix-Sum

누적합 문제인데 어떤 식으로 누적합을 써야할 지 모르겠어서..일단 그냥 브루트포스로 풀어봤다

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill){
    int answer = 0;
    for(int i=0;i<skill.size();i++){
        if(skill[i][0] == 1){
            for(int x = skill[i][1];x<=skill[i][3];x++){
                for(int y = skill[i][2];y <= skill[i][4];y++){
                    board[x][y] -= skill[i][5];
                }
            }
        } else{
            for(int x = skill[i][1];x<=skill[i][3];x++){
                for(int y = skill[i][2];y <= skill[i][4];y++){
                    board[x][y] += skill[i][5];
                }
            }
        }
    }

    for(int i=0;i < board.size();i++){
        for(int j=0;j<board[i].size();j++){
            if(board[i][j] > 0)answer++;
        }
    }
    return answer;
}

역시나..정확성은 다 맞지만 시간초과로 틀렸다

3-40분동안 봐도 누적합을 사용하면 된다는 것을 알지만 아이디어가 생각이 안나서..
https://blog.encrypted.gg/1031 이 분의 글을 참고하였다..!

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int arr[1001][1001]; //전역 변수 자동으로 0 초기화
int N,M;

int solution(vector<vector<int>> board, vector<vector<int>> skill){
    int answer = 0;
    N = board.size();
    M = board[0].size();

    //arr 배열에 skill 변화량 저장
    for(int i=0;i<skill.size();i++){
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int sk = skill[i][5];
        if(skill[i][0] == 1){
            arr[r1][c1] -= sk;
            arr[r1][c2+1] += sk;
            arr[r2+1][c1] += sk;
            arr[r2+1][c2+1] -= sk;
        } else{
            arr[r1][c1] += sk;
            arr[r1][c2+1] -= sk;
            arr[r2+1][c1] -= sk;
            arr[r2+1][c2+1] += sk;
        }
    }
    //스킬 변화량 누적합
    for(int x = 0; x< N+1;x++){
        for(int y = 0; y < M+1;y++){
            if(y!=0){
                arr[x][y] += arr[x][y-1];
            }
        }
    }
    for(int y = 0; y<M+1;y++){
        for(int x = 0; x < N+1;x++){
            if(x!=0){
                arr[x][y] += arr[x-1][y];
            }
        }
    }
    //파괴되지 않은 건물 확인
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(board[i][j] + arr[i][j] > 0)answer++;
        }
    }
    return answer;
}

이렇게 풀었더니 통과하였다.
진짜 코테 문제는 처음 풀어보는데 생각보다 알고리즘 생각해 내는 것이 어려운 것 같다. 좀 더 잘 정리해둬야겠다.