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

---

🔗 문제 링크

프로그래머스

---

💡 문제 풀이 및 해석

1. 매 skill마다 board를 바꾸면, 시간복잡도가 너무 증가한다. 따라서 매번 바꾸는 방식은 안된다.
2. 여기서 누적합 혹은 DP방식으로 풀어야 한다는 것을 알 수 있다.
3. 여기서 2차원 배열에서의 누적합으로 풀어야 하는데, 풀이 방식은 각 모서리에 마킹을 해두는 것이다.
4. Attack 기준으로 아래 코드에서도 볼 수 있듯이 4x4 사이즈에서는 5x5 사이즈의 임시 맵의 모서리에 마킹을 해둔다.
   MAP[r1][c1] -= degree;
MAP[r1][c2 + 1] += degree;
MAP[r2 + 1][c1] += degree;
MAP[r2 + 1][c2 + 1] -= degree;
5. 모든 skill에 대해서 임시 맵에 마킹을 해두었다면, 행과 열에 대해서 누적합을 진행한다. 방식은 아래 코드에서 //누적합이라고 해둔 부분과 같다.

---

⭐️ 정답 코드 및 설명

#include <string>
#include <vector>

using namespace std;

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

    // 0으로 채워지고, size가 +1인 임시 board
    vector<vector<int>> MAP(board.size() + 1, vector<int>(board[0].size() + 1, 0));

    for (vector<int> sk : skill) {
        int type = sk[0], r1 = sk[1], c1 = sk[2], r2 = sk[3], c2 = sk[4], degree = sk[5];
        if (type == 1) { // attack
            MAP[r1][c1] -= degree;
            MAP[r1][c2 + 1] += degree;
            MAP[r2 + 1][c1] += degree;
            MAP[r2 + 1][c2 + 1] -= degree;
        }
        else if (type == 2){ // 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로 풀어야 한다고 생각했지만, 2차원배열에서 누적합은 해본적이 없어서 일단 DP로 접근했었다. 하지만, DP로는 풀 수 있는 방식이 안보여서 누접합인데,,, 어떻게 풀어야 하나 고민을 많이 했다. 결국, 구글링을 통해 어떤 방식의 누적합인지 알았고 2차원 배열에서의 누적합 방식을 알고나서는 로직을 만드는데는 어렵지 않은 문제였다... 진짜 이런 누적합 문제,,, 간단한데 어렵다. 문제를 참 잘 만들었다고 생각했다.