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

 이 문제는 누적합을 이용해서 푸는 문제이다. 일단 board의 최대 크기는 1,000 * 1,000 이고, skill의 최대 길이는 250,000 이다. 최악의 경우에는 skill의 모든 값이 0,0 ~ 999,999까지를 변경하는 경우이고, 이 때 250,000 * 1,000 * 1,000 이기 때문에 당연히 시간 초과가 난다. 여기서 많은 경우를 생각해봤지만, 마땅한 알고리즘이 떠오르지 않아 해설을 봤고, 새로운 개념을 알 수 있었다.

 

 

 바로 누적합을 이용하는 것인데, [n1, n2] 까지의 범위 안에서 일정 숫자를 더해주고자 할 때, 반복문을 돌려 갱신하면  O(n) 시간이 걸린다. 하지만 [n1, n2 + 1] 까지 0이 저장되어있는 배열에서 n1의 위치에 더할 숫자 x를, n2 + 1 위치에 -x를 넣어주고 누적합 반복문을 돌리면 똑같은 결과를 낼 수 있다. 얼핏 보면 오히려 일을 두번 하는 것 같지만, 범위 안의 연산을 그때마다 하는게 아닌 범위에 대한 정보만을 저장하고 나중에 일괄 처리할 수 있다는 아이디어가 매우 중요하다. 이 아이디어를 사용하여 이 문제를 풀 수 있다.

 

 

0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0

  해당 2차원 배열에서 [0, 0] ~ [2, 2] 까지 n을 더한다고 가정하면 범위 정보를 저장하는 방법은 다음과 같다.

n	0	0	-n
0	0	0	0
0	0	0	0
-n	0	0	n

 이 상태에서 행 우선으로 먼저 누적합을 구하면 다음과 같이 된다.

n	n	n	0
0	0	0	0
0	0	0	0
-n	-n	-n	0

그 다음 열 우선으로 누적합을 구하면 다음과 같이 원하는 배열이 나오게 된다.

n	n	n	0
n	n	n	0
n	n	n	0
0	0	0	0

이를 그대로 문제에 적용하면 쉽게 문제를 풀 수 있다. 내 생각이지만 이 문제는 위의 테크닉을 알지 못하면 아마 그 자리에서 생각해내기에는 쉽지 않았을 것 같다. 

 

 

#include <string>
#include <vector>

using namespace std;

int acc[1003][1003];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    for (vector<int>& sk : skill) {
        int type = sk[0];
        int r1 = sk[1];
        int c1 = sk[2];
        int r2 = sk[3];
        int c2 = sk[4];
        int degree = sk[5];
        
        if (type == 1) {
            degree = -degree;
        }
        
        acc[r1][c1] += degree;
        acc[r1][c2 + 1] += -degree;
        acc[r2 + 1][c1] += -degree;
        acc[r2 + 1][c2 + 1] += degree;
    }
    
    for (int y = 0; y < 1003; y++) {
        for (int x = 0; x < 1002; x++) {
            acc[y][x + 1] += acc[y][x];
        }
    }
    
    for (int x = 0; x < 1003; x++) {
        for (int y = 0; y < 1002; y++) {
            acc[y + 1][x] += acc[y][x];
        }
    }
    
    for (int y = 0; y < board.size(); y++) {
        for (int x = 0; x < board[0].size(); x++) {
            if (board[y][x] + acc[y][x] >= 1) {
                answer++;
            }
        }
    }
    
    return answer;
}