문제

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

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

풀이

처음 문제를 읽자마자 와! 이건 정말 간단한걸? 생각하고 바로 풀어봤지만 역시나 효율성 테스트에서 전부 실패했다. 문제가 이렇게 쉬울리 없었다.

이 문제는 누적합을 이용하여 풀어야 효율성 테스트를 통과할 수 있었다.
그렇지않다면 skill 행의 길이 * board 크기 만큼의 연산이 필요해진다.

예시로
길이가 7이고 각 0으로 초기화된 배열 a가 있다.

a = [0, 0, 0, 0, 0, 0, 0]

이때 a[2:4]의 요소의 값을 2 만큼 더해주고 싶다면

[0, 0, 2, 0, 0, -2, 0]

로 표현한 뒤 누적합을 계산하면된다.

[0, 0, 2, 2, 2, 0, 0]

원했던 a[2:4]의 값에 2를 더한 배열이 되었다.

이 방법을 응용하여 이 문제에 적용하면된다.
문제에서는 2차원 배열을 이용한다.

[[0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

만약 (1,1) 에서 (3,4) 까지의 값을 3만큼 더하고 싶다면

[[0, 0, 0, 0, 0, 0],
 [0, 3, 0, 0, 0, -3],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, -3, 0, 0, 0, 3],
 [0, 0, 0, 0, 0, 0]]

로 표현한 뒤 각 행, 열을 차례로 누적합하여 계산하면 된다.
행 먼저 누적합하여 계산하면

[[0, 0, 0, 0, 0, 0],
 [0, 3, 3, 3, 3, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, -3, -3, -3, -3, 0],
 [0, 0, 0, 0, 0, 0]]

열을 누적합하여 계산하면

[[0, 0, 0, 0, 0, 0],
 [0, 3, 3, 3, 3, 0],
 [0, 3, 3, 3, 3, 0],
 [0, 3, 3, 3, 3, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

이 되어 원하는 결과를 얻을 수 있다.

문제를 풀 때 r2+1 과 c2+1이 board의 인덱스 범위에서 벗어나는 경우가 발생하여서
board의 행과 열보다 1씩 큰 2차원 배열 temp를 만든 뒤 temp에서 모든 누적합을 계산하고 마지막에 board에 더하여 계산하였다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    vector temp(board.size()+1, vector<int>(board[0].size()+1, 0));
    for (auto i: skill){
        int r1 = i[1];
        int c1 = i[2];
        int r2 = i[3];
        int c2 = i[4];
        int degree = i[5];

        if (i[0] == 1) degree *= -1; 

        temp[r1][c1] += degree;
        temp[r1][c2+1] -= degree;
        temp[r2+1][c1] -= degree;
        temp[r2+1][c2+1] += degree;

    }
    for (int i=0; i < temp.size(); i++){
        for (int j=1; j < temp[0].size(); j ++){
            temp[i][j] += temp[i][j-1];
        }
    }
    for (int i=1; i < temp.size(); i++){
        for (int j=0; j < temp[0].size(); j ++){
            temp[i][j] += temp[i-1][j];
        }
    }

    for (int i=0; i < board.size(); i++){
        for (int j=0; j < board[0].size(); j ++){
            if (board[i][j] + temp[i][j] > 0) 
                answer++;
        }
    }
    return answer;
}