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

 

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

프로그래머스

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

using namespace std;

/*
(0,0) ~ (1,1) n 표시 -> 행별로 열 누적합 -> 열별로 행 누적합
[n, 0, -n, 0]           [n, n, 0, 0]      [n, n, 0, 0] 
[0, 0, 0, 0]            [0, 0, 0, 0]      [n, n, 0, 0] 
[-n, 0, n, 0]           [-n, -n, 0, 0]    [0, 0, 0, 0] 
*/

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<vector<int>> info;
    info.resize(board.size()+1);
    for(int i=0; i<board.size()+1; i++) info[i].resize(board[0].size()+1);
    
    // 표시
    for(auto s : skill) {
        int degree = s[5];
        if (s[0] == 1) degree *= (-1);
        info[s[1]][s[2]] += degree;
        info[s[1]][s[4]+1] += degree * (-1);
        info[s[3]+1][s[2]] += degree * (-1);
        info[s[3]+1][s[4]+1] += degree;
    }
    
    // 행별로 열 누적합
    for(int i=0; i<info.size(); i++) {
        for(int j=0; j<info[i].size()-1; j++) info[i][j+1] += info[i][j];
    }
    
    // 열별로 행 누적합
    for(int j=0; j<info[0].size(); j++) {
         for(int i=0; i<info.size()-1; i++) info[i+1][j] += info[i][j];
    }
    
    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board[i].size(); j++) {
            if (board[i][j] + info[i][j] > 0) answer++;
        }
    }
    
    return answer;
}