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

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

내 해답

(1) 일반적인 for문 사용. 스킬을 처리할 때마다 2중 for문을 돌기 때문에 시간초과가 난다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    for(const auto& s : skill)
    {
        for(int r = s[1]; r <= s[3]; ++r)
            for(int c = s[2]; c <= s[4]; ++c)
            {
                int degree = s[0] == 1 ? -s[5] : s[5];
                board[r][c] += degree;
            }
    }
    
    for(int n = 0; n < board.size(); ++n)
        for(int m = 0; m < board[0].size(); ++m)
        {
            if(board[n][m] > 0)
                ++answer;
        }
    
    
    return answer;
}

 

(2) dp - 누적합 사용

 

누적합 과정

1. 누적합을 저장할 배열을 만든다.

2. 누적합을 적용할 영역의 첫번째 인덱스에 더할 값(-d)을 넣는다.

3. 누적합 영역밖에 더할 값을 상쇄할 값(+d)을 넣는다.

4. 가로-세로 방향으로 확장한다.

    4-1. 가로 방향 확장(→)

    4-2. 세로 방향 확장 (↓)

5. 누적합 배열 완성!

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    vector<vector<int>> dg(board.size()+1, vector<int>(board[0].size()+1));
         
    for(const auto& s : skill)
    {
        int degree = s[0] == 1 ? -s[5] : s[5];
        
        // 누적합
        dg[s[1]][s[2]] += degree;
        
        // 누적합 영역 밖 처리
        dg[s[1]][s[4]+1] -= degree; // 가로 영역 밖
        dg[s[3]+1][s[2]] -= degree; // 세로 영역 밖
        dg[s[3]+1][s[4]+1] += degree; // 가로x세로 영역 밖
    }
    
    // 누적합 가로 방향 확장
    for(int n = 0; n < dg.size(); ++n)
        for(int m = 1; m < dg[0].size(); ++m)
        {
            dg[n][m] += dg[n][m-1];
        }
    
    // 누적합 세로 방향 확장
    for(int m = 0; m < dg[0].size(); ++m)
        for(int n = 1; n < dg.size(); ++n)
        {
            dg[n][m] += dg[n-1][m];
        }
    
    // 파괴되지 않는 건물 체크
    for(int n = 0; n < board.size(); ++n)
        for(int m = 0; m < board[0].size(); ++m)
        {
            if(board[n][m] + dg[n][m] > 0)
                ++answer;
        }
    
    return answer;
}