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

---

🔗 문제 링크

프로그래머스

---

💡 문제 풀이 및 해석

1. 직사각형의 크기만큼 모두 더하면 최악의 경우 $$1000\times1000\times250000$$ 이라는 말도안되는 경우의 수가 발생하므로 다른 방법을 생각해야 한다.
2. 여기서 DP 아니면 누적합이 보통은 떠오를 텐데, 솔직히 문제 후기에서 말한듯이 둘 중 하나를 선택하고 생각하는 것은 개인의 능력이 아닐까 싶다. 이 문제는 제목에 써놓은 듯이 누적합 문제이다.
3. 일차원 누적합이 아닌 2차원 누적합이니 다른 방법이 필요한데 아래 만약, (0,0) (2,2) 에 5를 더한다고 하면, 아래와 같이 해서 행, 열 혹은 열, 행 순서로 누적합 해주면 된다. 코드를 보면 바로 이해가 될 것이다.

5 0 0 -5      5 5 5 0  
0 0 0 0      5 5 5 0  
0 0 0 0  =>  5 5 5 0
-5 0 0 5      0 0 0 0

---

⭐️ 정답 코드 및 설명

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;

    vector<vector<int>> MAP(board.size() + 1, vector<int>(board[0].size() + 1, 0));

    for (vector<int> sk : skill) {
        int r1 = sk[1], c1 = sk[2], r2 = sk[3], c2 = sk[4], degree = sk[5];
        if (sk[0] == 1) { // attack
            MAP[r1][c1] -= degree;
            MAP[r1][c2 + 1] += degree;
            MAP[r2 + 1][c1] += degree;
            MAP[r2 + 1][c2 + 1] -= degree;
        }
        else { // recovery
            MAP[r1][c1] += degree;
            MAP[r1][c2 + 1] -= degree;
            MAP[r2 + 1][c1] -= degree;
            MAP[r2 + 1][c2 + 1] += degree;
        }
    }
    // 누적합
    for (int y = 0; y < board.size(); y++) {
        for (int x = 0; x < board[0].size(); x++) {
            MAP[y][x + 1] += MAP[y][x];
        }
    }
    for (int x = 0; x < board.size(); x++) {
        for (int y = 0; y < board[0].size() - 1; y++) {
            MAP[y + 1][x] += MAP[y][x];
        }
    }

    // board에 더하기
    for (int y = 0; y < board.size(); y++) {
        for (int x = 0; x < board[0].size(); x++) {
            board[y][x] += MAP[y][x];
            if (board[y][x] > 0)answer++;
        }
    }
    return answer;
}

---

🤔 문제 후기

처음에는 이걸 전부 다 더하면 절대로 효율성 테스트에서 통과하지 못하기 때문에, 무식하게 더하는 방법은 없었다. 그러면 이런 문제를 해결할 방법은 DP 이거나 누적합 정도가 생각났는데, 누적합으로 어떻게 할까... 생각이 나지 않아서 DP문제라고 생각하였다. 그러다가 DP로 해결할 방법이 떠오르지 않아서 힌트를 얻고 풀려고 했는데, 누적합에 설명창에 아래와 같은 예시를 보고 바로 알았다. 알면 너무 쉽고, 모르면 생각하기가 어려운 문제가 아니였나 싶었다.

[5, 0, 0, -5]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-5, 0, 0, 5]