프로그래머스 파괴되지않은건물 c++ // dp, 구간합 효율적으로 구하는법

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

프로그래머스

1. 구간합 효율적으로 구하는법

1.1 1차원예시

[ 0 , 0 , 0 , 0 , 0] 에 0~3idx까지 a를 더하고싶다

1. [a, 0, 0, 0, -a] 배열 생성

2. ->쪽으로 누적합을구함 

3. a배열과 원본배열을 더함. 끝.

 

1.2 2차원예시

네모친구간에 a를 더하고싶다.

 

 

1. 좌측위, 우측아래에 a를 더하고 / 우측위, 좌측아래에 -a를 더한다.

2. ->, 아래쪽으로 누적합을구함

3. 그결과과 원본을 더함. 끝.

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;
int a[1004][1004],ret;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int n=board.size();
    int m=board[0].size();
    //1. 누적합배열생성 
    //where out of index? -> a를 크게선언[1004]했으므로 상관없음!
    for(auto v : skill){
        int type=v[0], r1=v[1],c1=v[2],
                r2=v[3],c2=v[4],degree=v[5];
        if(type==1) degree= -degree;
        a[r1][c1]+=degree;
        a[r2+1][c2+1]+=degree;
        a[r1][c2+1]-=degree;
        a[r2+1][c1]-=degree;
    }
    
    //누적합더하기 ->, 아래
    for(int i=0;i<n;++i){
        for(int j=1;j<m;++j){
            a[i][j]+=a[i][j-1];
        }
    }
    //누적합더하기  아래
    for(int i=1;i<n;++i){
        for(int j=0;j<m;++j){
            a[i][j]+=a[i-1][j];
        }
    }
    
    //board와 a 더하기
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            board[i][j]+=a[i][j];
        }
    }
    
    //1이상인 갯수세기
    int ret=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(board[i][j]>=1) ret++;
        }
    }
    return ret;
}