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

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

프로그래머스

 

누적합을 통해 효율성 확보

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

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

누적합? 

문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있습니다. 

 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int n = board.size(), m = board[0].size();
    vector<vector<int>> acc(n+1, vector<int>(m+1, 0));
    
    for(int i=0; i<skill.size(); i++){
        int val = skill[i][5];
        if(skill[i][0] == 1) val = -val;
        
        acc[skill[i][1]][skill[i][2]] += val;
        acc[skill[i][3]+1][skill[i][2]] -= val;
        acc[skill[i][1]][skill[i][4]+1] -= val;
        acc[skill[i][3]+1][skill[i][4]+1] += val;
    }
    
    for(int i=0; i<n+1; i++)
        for(int j=1; j<=m; j++)
            acc[i][j] += acc[i][j-1];
    
    for(int j=0; j<m+1; j++)
        for(int i=1; i<=n; i++)
            acc[i][j] += acc[i-1][j];
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(board[i][j] + acc[i][j] > 0) answer++;
            
            
    return answer;
}