[프로그래머스] 파괴되지 않은 건물 C++ - 2차원 누적합

🧐문제

https://programmers.co.kr/learn/courses/30/lessons/92344
(👉🏻자세한 예시는 링크 문제 참고!)

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

• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

• 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.

입출력

board	skill	result
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]	[[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]	10
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6

풀이

🐥처음에 푼 방식
처음에는 효율성을 생각하지 않고 가장 기본적인 방식인 skill 벡터만큼 탐색하며 board에 값을 변경해주었다. => 역시나 정확도 100 / 효율성 0
(브루투 포스로 풀면 O(N M K)으로 시간초과!)

🙉2차원 누적합을 이용한 방식
시작점에 +N 끝점에 -N을 표기하고 이를 한번에 계산하는 방법으로 풀이

해당하는 범위의 꼭지점에 degree 값을 채워준다.
그 후, 왼쪽에서 오른쪽 / 위에서 아래로 더해주며 2차원 배열을 완성하는 방식으로 풀면 된다.

코드

#include <string>
#include <vector>

using namespace std;
int map[1010][1010];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int n = board.size();
    int m = board[0].size();
    
    for(auto v : skill) {
        int degree = v[5], r1 = v[1], c1 = v[2],
        r2 = v[3], c2 = v[4];
        if(v[0]==1) degree *= -1;
        
        //꼭지점을 표시하는 부분
        map[r1][c1] += degree;
        map[r1][c2+1] -= degree;
        map[r2+1][c1] -= degree;
        map[r2+1][c2+1] += degree; 
    }
    
    //오른쪽으로 이동하며 값을 더해준다.
    for(int i = 1; i < n; i++)
        for(int j = 0; j < m; j++)
            map[i][j] += map[i-1][j];
    
    //아래로 이동하며 값을 더해준다.
    for(int i = 0; i < n; i++)
        for(int j = 1; j < m; j++)
            map[i][j] += map[i][j-1];
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            if(map[i][j] + board[i][j] > 0)
                answer++;
        }
    
    
    
    return answer;
}

코드와 같이 r1,r2,c1,c2 값으로 꼭지점의 시작과 끝을 n과 -n으로 표시해준다. 그 후 왼->오, 위->아래로 이동하며 배열에 저장된 값을 합해준다.

---

🕶회고
2차원 누적합을 처음 접해봐서 생각하지 못했다. 관련된 문제를 풀어봐야겠다!
https://www.acmicpc.net/problem/11660