프로그래머스 (C/C++, Java) 92344 : 파괴되지 않은 건물

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

---

풀이

누적합을 이용하여 풀어야겠다는 생각을 했지만, 2차원 배열에서의 누적합은 어떻게 해야 할지 몰라 다른 분들의 풀이를 참고했다. 

출처 : https://kimjingo.tistory.com/155

위의 그림과 같이 행과 열을 기준으로 누적합을 총 2번 계산한다. 이를 위해서 누적합 배열을 선언할 때 네 모서리에 각각 값을 넣어주어야 한다.

N의 데미지를 입는다 가정했을 때,

먼저 행을 기준으로 일차원 배열에서와 동일하게 데미지를 입는 시작 부분에 -N, 데미지를 입는 부분 + 1 열에 +N을 더해준다.

다음으로는 열을 기준으로 데미지 입는 부분의 범위를 정할 것인데 그림에서 2번째 단계까지 시행한 후 열 기준으로 누적합을 계산해야 하기에 행 기준으로 데미지를 입기 시작하는 부분베 +N 값을 저장하고 입지 않는 부분에 -N을 더해준다.

이를 통해 열 기준으로 누적합을 시행했을 때 데미지를 입는 구역을 정할 수 있고, 결과적으로 2차원 배열에서의 누적합을 구할 수 있다.

 

---

C/C++ 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
        int r = board.size(), c = board[0].size();
        vector<vector<int>> allDamages(r + 1, vector<int>(c + 1, 0));

        for (const auto& s : skill) {
            int damage = (s[0] == 1) ? -s[5] : s[5];

            allDamages[s[1]][s[2]] += damage;
            allDamages[s[1]][s[4] + 1] -= damage;

            allDamages[s[3] + 1][s[2]] -= damage;
            allDamages[s[3] + 1][s[4] + 1] += damage;
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                allDamages[i][j + 1] += allDamages[i][j];
            }
        }

        for (int j = 0; j < c; j++) {
            for (int i = 0; i < r; i++) {
                allDamages[i + 1][j] += allDamages[i][j];
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] + allDamages[i][j] > 0) answer++;
            }
        }
        return answer;
}

 

Java 코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int r = board.length, c = board[0].length;
        int[][] allDamages = new int[r + 1][c + 1];
        
        // 누적합 배열 선언
        for (int[] s : skill) {
            int damage = s[0] == 1 ? -s[5] : s[5];
            
            allDamages[s[1]][s[2]] += damage;
            allDamages[s[1]][s[4] + 1] -= damage;
            
            allDamages[s[3] + 1][s[2]] -= damage;
            allDamages[s[3] + 1][s[4] + 1] += damage;
        }
        
        // 행 누적합 결과 갱신
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                allDamages[i][j + 1] += allDamages[i][j];
            }
        }
        
        // 열 누적합 결과 갱신
        for (int j = 0; j < c; j++) {
            for (int i = 0; i < r; i++) {
                allDamages[i + 1][j] += allDamages[i][j];
            }
        }
        
        // 파괴되지 않은 건물 확인
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] + allDamages[i][j] > 0) answer++;
            }
        }
        return answer;
    }
}