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

< 해설 >

보자마자 간단히 for문으로 풀면 당연히 시간초과가 나겠군. 이라고 생각이 든 문제였다.

보통 이런문제는 누적합으로 문제를 풀기 때문에 누적합으로 접근을 해야하는 문제임을 확신하고 질문하기 들어가보니까 역시 누적합으로 접근해야 하는 문제였다.

누적합은 많은 연산을 딱 한번만 진행하는 것. 건물을 부수고 수리하는 많은 skill 배열을 한번만 돌아서 연산해야할 수를 정해준다. 각 skill 마다 최대 1000*1000 행렬을 돌지 않아도 되는것. 

 

가로세로의 누적합을 각각 계산해야해서 인덱스를 조절해주는게 좀 까다로웠다.

예를들어 [ 0, -2, -2, -2 ] 이렇게 데미지가 들어간다면 실제 배열은 [ 0, -2, 0, 0, 2 ] 와 같이 처리해주어야 하니 말이다. 이게 가로 누적합은 쉬운데 세로 누적합은 더 까다롭기도 하다. 직사각형으로 데미지가 들어간다면 좌상단의 좌표에서 x값은 하나 밑에서부터 시작해야하기 때문. (중복 누적방지) 그림으로 따지면 아래와 같다.

빨간색의 영역이 우리가 원하는 데미지 영역이라고 가정하자. 그럼 좌상단의 위치에서 -2 (입힐 데미지의 크기)를 만난다. 그럼 그 뒤의 값은 -2가 계속 적용된다. 그리고 영역을 벗어나면 +2 를 만나 -2 + 2 =0 으로 입힐 데미지는 0이 된다.

이렇게 가로의 누적합을 3줄에 걸쳐 적용하면 이제 데미지를 12칸 다 입히게 된다. 그러면 그 다음줄 (배열을 넘어가게 됨)은 가장 첫 칸에 +2를 해서 가로줄과 동일한 방법으로 세로줄의 데미지도 0으로 만들어준다. 세로줄 마지막 것도 마찬가지.

이러면 skill 을 한번만 돌고 임의의 누적합 베이스를 만들수 있다. 만든 누적합 베이스를 가지고 가로세로 각각 누적합을 처리해 준 뒤 board 배열을 한번 돌아 계산해 주면 된다.

2차원 누적합이라는 처음 보는 개념이 등장해서 조금 어려울 수 있다. 하지만 DP문제를 좀 풀었어서 누적합의 개념은 잘 알고있었기 때문에 이해하지 못할 정도는 아니었다.

 

< 문제 >

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.

예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

... (생략)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

 

< 풀이 >

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int boardY = board[0].size();
    int boardX = board.size();
    int arr[1001][1001] = {0,};
    
    // arr 배열에 누적합을 일단 만들어줌..
    for(auto s : skill)
    {
        int multi = 1;
        if(s[0] == 1)
            multi = -1;
        
        // 가로 누적합
        arr[s[1]][s[2]] += s[5] * multi;
        arr[s[1]][s[4]+1] -= s[5] * multi;
        
        // 세로 누적합
        arr[s[3]+1][s[2]] -= s[5] * multi;
        arr[s[3]+1][s[4]+1] += s[5] * multi;  
    }
    
    for(int i=1; i< board.size(); i++)
        for(int j=0; j<board[0].size(); j++)
            arr[i][j] += arr[i-1][j];
    
    for(int i=0; i< board.size(); i++)
        for(int j=1; j< board[0].size(); j++)
            arr[i][j] += arr[i][j-1];
    
    for(int i=0; i< board.size(); i++)
        for(int j=0; j< board[0].size(); j++)
        {
            if((arr[i][j] + board[i][j]) > 0)
                answer++;
        }
        
    return answer;
}