파괴되지 않은 건물 [Lv. 3]

프로그래머스

행렬 모양의 맵이 있고 각 칸마다 건물들이 있을 때 직사각형 범위의 스킬을 사용합니다.

스킬은 공격과 회복이 있으며 모든 스킬이 종료된 이후에 살아남은 건물의 수를 찾는 문제입니다.

문제 자체는 간단하지만 시간 제한이 있기 때문에 고민을 해봐야 하는 문제입니다.

 

풀이 방법

결론부터 말하자면 누적합을 응용하면 됩니다.

1차원 배열을 예로 들겠습니다.

arr = [5] [ ] [ ] [-5] [ ] [ ] [ ] [ ] [ ] [ ];

 

0 ~ 2까지 5의 데미지를 주는 스킬을 사용했을 때

위 처럼 시작점과 끝점 + 1에 값을 입력해준 후 누적합을 적용하면

arr[i] += arr[i -1];

arr = [5] [5] [5] [0] [0] [0] [0] [0] [0] [0];

 

하나의 스킬을 사용할때는 최적화의 의미가 없지만 여러개의 스킬을 사용한다면

이야기가 달라집니다.

0 ~ 2  [ -5 ] =>> [-5] [-5] [ 5] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0]
1 ~ 5  [  3 ] =>> [ 0] [ 3] [ 3] [ 3] [ 3] [ 3] [-3] [ 0] [ 0] [ 0] [ 0] [ 0]
3 ~ 10 [  2 ] =>> [ 0] [ 0] [ 0] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [-2]
6 ~ 7  [  4 ] =>> [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 4] [ 4] [-4] [ 0] [ 0] [ 0]
0 ~ 7  [ -4 ] =>> [-4] [-4] [-4] [-4] [-4] [-4] [-4] [-4] [ 4] [ 0] [ 0] [ 0]

arr = [-9] [ -6] [  4] [  1] [ 1] [ 1] [-1] [ 2] [ 2] [ 2] [ 2] [-2]
=>>>  [-9] [-15] [-11] [-10] [-9] [-8] [-9] [-7] [-5] [-3] [-1] [-3]

모든 스킬을 하나의 배열로 만들고 이것을 기존의 배열과 더해주기만 하면 되기 때문에

시간적으로 훨씬 빠릅니다. 

 

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skills) {
    int answer = 0;
    vector<vector<int>> b(board.size() + 1, vector<int>(board[0].size() + 1));
    
    for (auto skill : skills)
    {
        int type = skill[0];
        int r1 = skill[1];
        int c1 = skill[2];
        int r2 = skill[3];
        int c2 = skill[4];
        int degree = skill[5];
            if (type == 1)
                degree *= -1;
        
        b[r1][c1] += degree;
        b[r1][c2+1] -= degree;
        b[r2+1][c1] -= degree;
        b[r2+1][c2+1] += degree;
    }
    
    for (int i = 0; i < b.size(); i++){
        for (int j = 1; j < b[i].size(); j++)
            b[i][j] += b[i][j - 1];      
    }
    
    for (int i = 1; i < b.size(); i++){
        for (int j = 0; j < b[i].size(); j++)
            b[i][j] += b[i - 1][j];
    }
    
    
    for (int i = 0; i < board.size(); i++){
        for (int j = 0; j < board[i].size(); j++)
            if (board[i][j] + b[i][j] > 0)
                answer++;
    }
    
    return answer;
}