[프로그래머스] Level 3. 파괴되지 않은 건물

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

프로그래머스

 

 

2D Prefix Sum, 즉 누적합을 이용해 문제를 풀어야 통과되는 문제이다.

핵심은 누적합 배열인 diff를 만드는것이다.(r1,c1)에서  (r2,c2) 까지 1을 더한다고햇을때 , 작업은 다음과같다.

1. diff[r1][c1] 에 +1 을 저장한다. 

2. diff[r1][c2+1] 에 -1을 저장한다.

 

1~2번은, 가로로검사할때 diff[x][y] += diff[x][y-1] 을 수행할 경우 딱 c1~c2 까지 +1처리가된다.

 

3. diff[r2+1][c1] 에 -1을 저장한다.

3. diff[r2+1][c2+1] 에 1을 저장한다.

 

 

이렇게하면 가로먼저검사하든, 세로먼저 검사하든 정확한 변화량이 저장된다.

 

진짜어려운문제였다. 

#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int N = board.size();
    int M = board[0].size();
    
    // 누적합을 저장할 배열 생성 (N+1, M+1 크기로 생성하여 경계 처리)
    vector<vector<int>> diff(N + 1, vector<int>(M + 1, 0));
    
    // 1. 차이 배열(diff) 업데이트
    for (auto &s : skill) {
        int type = s[0];  // 1: 공격, 2: 회복
        int r1 = s[1], c1 = s[2], r2 = s[3], c2 = s[4], degree = s[5];

        int effect = (type == 1) ? -degree : degree;  // 공격이면 음수, 회복이면 양수

        diff[r1][c1] += effect;
        diff[r1][c2 + 1] -= effect;
        diff[r2 + 1][c1] -= effect;
        diff[r2 + 1][c2 + 1] += effect;
    }

    // 2. 누적합 적용 (행 기준)
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < M; j++) {
            diff[i][j] += diff[i][j - 1];
        }
    }

    // 3. 누적합 적용 (열 기준)
    for (int j = 0; j < M; j++) {
        for (int i = 1; i < N; i++) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    // 4. 원본 board에 적용하고 생존한 건물 개수 계산
    int answer = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            board[i][j] += diff[i][j];
            if (board[i][j] > 0) answer++;
        }
    }

    return answer;
}