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

문제

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

프로그래머스

 

 

 

입출력

 

 

---

아이디어

 

- 누적합 

코드 

 

class Solution {
    // skill
    public int solution(int[][] board, int[][] skill) {
        int[][] diff = new int[board.length+1][board[0].length+1];
        int answer = 0;
        for(int[] s : skill) {
            int type = s[0] == 1 ? -1 : 1; // type 1 적의 공격, type 2 아군의 회복 스킬 
            int r1 = s[1], c1 = s[2], r2 = s[3], c2 = s[4];
            int degree = s[5]; 
            diff[r1][c1] += type * degree;
            diff[r2+1][c2+1] += type * degree; 
            diff[r1][c2+1] -= type * degree; // 누적합할 때 끝에서 곱함 
            diff[r2+1][c1] -= type * degree;
        }
        
        for(int i = 0; i <= board.length; i++){
            for(int j = 1; j <= board[0].length; j++){
                diff[i][j] += diff[i][j-1];
            }
        }
        
        for(int j = 0; j <= board[0].length; j++){
             for(int i = 1; i <= board.length; i++){
                diff[i][j] += diff[i-1][j];
            }
        }
        int cnt = 0;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                board[i][j] += diff[i][j];
                cnt += board[i][j] >= 1 ? 1 : 0;
            }
        }
        return cnt;
    }
}