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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 누적합 
풀이 시간 : 1시간 30분 

문제 풀이 

문제의 설명 자체는 간단하다. N x M 크기의 행렬 모양의 게임 맵에는 내구도를 가진 건물이 각 칸마다 존재하는데, 두 개의 스킬(파괴, 회복)을 사용하여 특정 구간의 건물에 적용한 뒤, 내구도가 0 이상인 건물의 개수를 return하는 것이다.

 

하지만 큰 문제는 각 입력의 범위에 존재한다.

먼저 행렬의 범위는 $N, M ≤ 1000$ 이고, $skill 의 개수(K) ≤ 250000$이기 때문에, 완전탐색으로 문제를 풀어나갈 경우에 최악의 경우, $O(N * M * K) = 250000 * 1000 * 1000$으로 시간초과가 발생함이 틀림없어진다.

 

따라서 이를 해결하기 위해 누적합 공식을 사용할 것이다. 

아이디어는 간단하다. 각 칸이 받을 수 있는 모든 데미지를 구한 뒤, 초기 게임 맵 정보와 더해 비교하는 것이다. 하지만, 문제는 누적합을 어떻게 구할 것인가 ? 이다. 

 

특정 구간에서 누적합을 구하기 위해서는 다음과 같은 방법을 사용할 것이다.

먼저, 1차원 배열을 예시로 들어보자.

 

ex) n = 5의 1차원 배열에서 0 ~ 2번 인덱스 사이의 값을 2만큼 빼고 싶다.

1. 시작 인덱스에는 빼고자 하는 값을 입력하고, 종료 인덱스 + 1 위치에는 빼고자 하는 값의 부호를 바꾼 값을 입력한다.

2. 이후, 시작 인덱스부터 끝까지 누적합을 진행해준다.

결과를 확인해보면, 0 ~ 2번 인덱스까지 2의 값이 빼진 것을 확인할 수 있다.

 

이를 2차원으로 생각해보면 다음과 같다.

ex) n = 3, m = 3인 2차원 배열에서 (0, 1) ~ (2, 2) 구간의 값을 4만큼 더하고 싶다.

1. 시작 인덱스(0, 0)과 종료 인덱스 (2 + 1, 2 + 1) 에는 더하고자 하는 값을 입력한다.

2. (시작 행, 종료 열 + 1), (종료 행 + 1, 시작 열) 에는 더하고자 하는 값을 부호를 바꿔 입력한다.

=> 여기서, 종료 지점에 4를 더해주는 이유는 누적합을 행 한번, 열 한 번 계산해 줄 때, 종료 인덱스에서는 중복 계산이 이루어지기 때문에 중복된 계산을 방지하기 위해서 한 번 값을 더해주는 과정이라고 생각하면 된다.

행을 기준으로 먼저 더한 결과(왼)와 열을 기준으로 한 번 더 누적합을 진행한 결과(오)

 

이렇게 모든 skill에 대해서 누적합을 계산해준 뒤, 최종 데미지를 초기 board와 더해주어 0보다 내구도가 큰 건물의 count를 세주면 된다. 

해당 방법으로 문제를 해결할 시, 시간복잡도는 $O(K + NM)$이 소요되어 제한시간 내에 문제를 해결할 수 있다.

 

코드

/*
명령 = 25만 -> O(n) or O(nlogn)안에 처리하는 것이 관건이다.
범위 찾아서 반복문 돌리면 250000 * 1000 * 1000 => 시간초과

- 백준 : 개똥벌레 문제처럼 누적합을 진행해주면 된다.
    -> 해당 문제에서는 출발지 = -1, 도착지 + 1 = 1로 설정하여 누적합을 진행했었음
해당 문제는 위 문제의 2차원 풀이를 진행하면 된다.

ex) 3 x 3에서 (0, 0) -> (2, 2) 까지 -2라면
[-2, 0, 0, 2]
[0, 0, 0, 0]
[0, 0, 0, 0]
[2, 0, 0, -2]   해줘야함
# 마지막(3, 3)에 -2 해주는 이유 : 행 x 열 모두 누적합 진행할 때, 두 번 값이 겹치기 때문에 한 번은 빼주어야 함
    -> 이 이유는 2차원 누적합 문제를 풀 때 공통으로 적용되는 사항임
*/

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int n, m;
int prefixSum[1001][1001] = {0, };

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    n = board.size();
    m = board[0].size();
    
    // 모든 skill에 대해 누적합 진행
    for (int i = 0; i < skill.size();i++){
        // 뺄셈
        if (skill[i][0] == 1) {
            prefixSum[skill[i][1]][skill[i][2]] -= skill[i][5];
            prefixSum[skill[i][1]][skill[i][4] + 1] += skill[i][5];
            prefixSum[skill[i][3] + 1][skill[i][2]] += skill[i][5];
            prefixSum[skill[i][3] + 1][skill[i][4] + 1] -= skill[i][5];
        }  
        // 덧셈
        else {
            prefixSum[skill[i][1]][skill[i][2]] += skill[i][5];
            prefixSum[skill[i][1]][skill[i][4] + 1] -= skill[i][5];
            prefixSum[skill[i][3] + 1][skill[i][2]] -= skill[i][5];
            prefixSum[skill[i][3] + 1][skill[i][4] + 1] += skill[i][5];
        }
    }
    
    
    // 누적합 생성하기 (행 x 열 더해주기)
    // 행
    for (int i=0;i<n;i++){
        for (int j=1;j<m;j++){
            prefixSum[i][j] += prefixSum[i][j - 1];
        }
    }
    // 열
    for (int i=0;i<m;i++){
        for (int j=1;j<n;j++){
            prefixSum[j][i] += prefixSum[j - 1][i];
        }
    }
    
    
    // 원래 배열과 값 더해주며 0보다 큰 값 answer에 더해주기
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (board[i][j] + prefixSum[i][j] > 0)
                answer++;
        }
    }
    
    return answer;
}

배운 점 

해당 문제에 접근하는 데 매우 오랜 시간이 걸려 결국 풀이를 참고한 문제이다. . .

하지만 해당 문제가 누적합임을 확인한 뒤 바로 떠오른 문제가 백준에 있다. (백준_3020_개똥벌레)

해당 문제 역시 특정 구간에 대한 누적합을 진행하여 최솟값을 구하는 문제로 풀이 방법이 비슷하기 때문에 다시 한 번 풀어보면 좋을 것 같다 !