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

핵심은 누적합 / 처음에 1차원배열로 변환시켜서 구현했다가 시간초과 떴고, 2차원 배열에서 구현하니 통과

* 또한, 누적합 처리과정에서 반복문의 시작지점을 잘 지정해주어야 한다.(디버깅하면서 오류발견했음)

 

    #include <string>
    #include <vector>
    #include<iostream>
    using namespace std;
    /*
    <문제>
    N*M행렬모양 게임 맵에서 각 칸은 내구도를 가짐
    적은 직사각형 구역으로 내구도를 깎고,
    아군은 직사각형 구역으로 내구도를 높임
    공격과 회복이 모두 끝난 후, 파괴되지 않은 건물 개수를 return
 
    <입력> 
    2차원 정수 배열 board(건물의 내구도를 나타냄)
    2차원 정수 배열 skill(공격 또는 회복 나타냄)
      *board는 N*M, 각각 1000 이하, 내구도는 1000이하 / skill은 최대 25만
      *skill은 type, r1, c1, r2, c2, degree형태로 한줄씩 여러개 주어짐
       (type은 1(공격)또는2(회복), 뒤의 4개는 각 좌표, degree는 최대 500)
 
    <출력>
    최후에 파괴되지 않은 건물 수 return
 
    <풀이>
    누적합 이용
    배열을 1차원 배열로 쭉 나열한 다음에, (a, b) - a부터 b까지 데미지처리를 양 끝단에서만 처리해주면 O(1)시간에 처리 가능
    -> 굳이 1차원 배열일 필요가 없음 / 2차원에서 구현하기
 
    */
 
    void setBoard(vector< vector<int> > &sumboard, int a, int b, int c, int d, int degree, int hang, int yeol) {
        //(a, b) ~ (c, d)를 세팅
        //이차원 : (a, b), (a, d+1), (c+1, b), (c+1, d+1)
        sumboard[a][b] += degree; 
        if (d + 1 < yeol) sumboard[a][d + 1] -= degree;
        if (c + 1 < hang) sumboard[c + 1][b] -= degree;
        if (c + 1 < hang && d + 1 < yeol) sumboard[c + 1][d + 1] += degree;
    }
 
    int solution(vector<vector<int>> board, vector<vector<int>> skill) {
        int answer = 0;
        int hang = board.size();    //행 수(즉, 세로길이)
        int yeol = board[0].size(); //열 수(즉, 가로길이)
        //(a, b) ~ (c, d) -> a<=c, b<=d 로 주어짐
 
        vector<vector<int>> sumboard(hang, vector<int>(yeol, 0));   //2차원 누적합 벡터
    
        for (int i = 0; i < skill.size(); i++) {    //skill 수만큼 반복
            int degree = skill[i][5]; if (skill[i][0] == 1) degree *= -1;   //데미지 저장(때에 따라 양수)
            setBoard(sumboard, skill[i][1], skill[i][2], skill[i][3], skill[i][4], degree, hang, yeol); //누적합 보드 저장
        }
  
        //sumboard 누적합으로 바꾸기
        for (int i = 0; i < hang; i++) {    //i는 0부터, j는 1부터 시작함에 주의
            for (int j = 1; j < yeol; j++) {
                sumboard[i][j] += sumboard[i][j - 1];
            }
        }
        for (int j = 0; j < yeol; j++) {    //i는 1부터, j는 0부터 시작함에 주의
            for (int i = 1; i < hang; i++) {
                sumboard[i][j] += sumboard[i - 1][j];
            }
        }
 
        //sumboard에 기존 배열값 더하기
        for (int i = 0; i < hang; i++)
            for (int j = 0; j < yeol; j++)
                sumboard[i][j] += board[i][j]; //sumboard에 각 기존 값 더하기
   
 
        //sumboard 보면서 파괴여부 판단
        for (int i = 0; i < hang; i++)
            for (int j = 0; j < yeol; j++)
                if (sumboard[i][j] >= 1) answer++;
  
        return answer;
    }
 
    int main() {
    //  vector<vector<int>> board = { {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5} };
    //  vector<vector<int>> skill = { {1, 0, 0, 3, 4, 4}, {1, 2, 0, 2, 3, 2}, {2, 1, 0, 3, 1, 2}, {1, 0, 1, 3, 3, 1} };
 
        vector<vector<int>> board = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
        vector<vector<int>> skill = { {1, 1, 1, 2, 2, 4}, {1, 0, 0, 1, 1, 2}, {2, 2, 0, 2, 0, 100} };
        cout << solution(board, skill) << endl;
        return 0;
    }