프로그래머스 문제 - 파괴되지 않은 건물

프로그래머스 파괴되지 않은 건물 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

N X M 크기의 게임 맵이 있으며, 각 칸마다 내구도를 가진 건물이 하나씩 존재합니다.
적은 이 건물들을 공격하여 파괴시키려고 하며, 아군은 건물들을 회복시켜 내구도를 높이려고 합니다.
이미 파괴된 건물이라도 회복시켜 건물을 복구시킬 수 있습니다.
적의 공격과 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 구해야합니다.

문제 풀이

공격이나 회복의 범위를 보며 더하는 방법이 있지만, 효율성을 검사하는 문제였기에 단순하게 더하고 빼서 통과할 수는 없는 문제입니다.
효율성을 해결할 방법을 찾지 못해 해설을 조금 참고하였더니 누적합으로 문제를 해결한다는 것을 알게 되었습니다.
https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/
예를 들어 [0, 0, 0, 0, 0]인 1차원 배열에 0번째 인덱스부터 3번째 인덱스까지 -2를 한다고 하면
for문을 이용하여 각 부분에 -2를 하는 것이 아닌 값을 바꿔줄 첫 인덱스에 -2를 넣어주고 마지막 인덱스의 다음 인덱스에 2를 넣어줍니다
그렇게 되면 [-2, 0, 0, 0, 2]처럼 배열에 만들어집니다.
이후 왼쪽부터 오른쪽으로 두번째 인덱스에 첫번째 인덱스를 더해주고, 세번째 인덱스에 두번째 인덱스를 더해주며 순서대로 끝가지 누적합을 진행시켜주면 원하는 배열인 [-2, -2, -2, -2, 0]이 만들어집니다.
즉, 값을 바꿔줄 첫 인덱스에 값을 넣어주고 마지막의 다음 인덱스에 (값 * -1)을 넣어준 후 이후에 누적합을 진행하면 원하는 배열을 만들어 낼 수 있습니다.
이러한 방법을 2차원 배열에 적용시켜주면 됩니다.
예를 들어 4 X 4크기의 맵에 (0,1)~(3,3)까지 2의 공격을 한다고 생각한다면
0 -2 -2 -2
0 -2 -2 -2
0 -2 -2 -2
0 -2 -2 -2
맵에 이러한 공격을 가할 것입니다.
하지만 위의 방식처럼 기존 맵보다 1칸씩 더 늘려 값을 넣어준다면
0 -2 0 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 2 0 0 -2
과 같은 맵이 됩니다.
이후에 계산을 진행하게 되면 맨 왼쪽부터 차례대로 누적합을 진행시켜줍니다. 그러면
0 -2 -2 -2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 2 2 2 0
이 나오게 됩니다. 이후에 맨 위에서 아래로 누적합을 다시 진행시켜준다면
0 -2 -2 -2 0
0 -2 -2 -2 0
0 -2 -2 -2 0
0 -2 -2 -2 0
0 0 0 0 0
이라는 맵이 나오게 되며 원하는 값을 얻어낼 수 있습니다.

이러한 방식과 같이 맵을 하나 만들어 모든 공격과 회복들의 값을 저장해준 후 맵을 완성시켜줍니다.
이후 처음에 주어진 맵에 더해주며 0보다 큰 값들의 수를 구해주면 됩니다.

전체 코드

2차원 배열 내에서 누적합을 하는 방법을 알 수 있었습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    vector<vector<int>> building(board.size()+1, vector<int>(board[0].size()+1, 0));
    
    //건물의 공격과 회복을 배열에 저장해둠
    for(int idx = 0; idx < skill.size(); idx++)
    {
        if(skill[idx][0] == 1)
        {
            building[skill[idx][1]][skill[idx][2]] += -skill[idx][5];
            building[skill[idx][1]][skill[idx][4]+1] += skill[idx][5];
            building[skill[idx][3]+1][skill[idx][2]] += skill[idx][5];
            building[skill[idx][3]+1][skill[idx][4]+1] += -skill[idx][5];
        }else{
            building[skill[idx][1]][skill[idx][2]] += skill[idx][5];
            building[skill[idx][1]][skill[idx][4]+1] += -skill[idx][5];
            building[skill[idx][3]+1][skill[idx][2]] += -skill[idx][5];
            building[skill[idx][3]+1][skill[idx][4]+1] += skill[idx][5];
        }
    }
    //건물들이 부셔졌는지 확인
    for(int i = 0; i < board.size(); i++)
    {
        int sum = 0;
        for(int j = 0; j < board[i].size(); j++)
        {            
            sum += building[i][j];
            building[i][j] = sum;
            if(i != 0)
                building[i][j] += building[i-1][j];
            
            if(board[i][j] + building[i][j] >= 1)
                answer++;
        }
    }
    
    return answer;
}

출저

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