[구간합] 파괴되지 않은 건물 - 2022 KAKAO BLIND RECRUITMENT

해결 방법

정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, 2차원 누적합 알고리즘을 사용하지 않는다면 효율성 테스트에서 통과하기 힘들 것이다.

 

필자는 데미지 범위를 나타내는 벡터와 데미지를 나타내는 벡터 총 2개의 벡터를 만들어서 해결했다.

입출력 예 #1를 기반으로 해결 방법을 설명해보겠다.

 

데미지 범위 벡터(damage_pos)

먼저, 데미지 범위 벡터의 모든 요소는 0으로 초기화해둔다.

(r1, c1)부터 (r2, c2)까지 degree 만큼의 공격을 받았다고 해보자.

이 때는 damage_pos의 (r1, c1), (r2+1, c2+1)에는 degree만큼 빼주고, (r1, c2+1), (r2+1, c1)에는 degree만큼 더해준다.

이를 그림으로 나타내면 다음과 같다. 회색 부분은 (r1, c1)부터 (r2, c2)까지의 범위다.

이런 과정을 수행하는 이유는 나중에 누적합을 편하게 구하기 위함이다.

degree만큼 빼주는 것은 범위가 끝났다는 것을 의미한다. 그리고 (r2+1, c2+1)에 degree를 더하는 이유는 누적합을 구할 때 앞에서 degree를 2번 빼줄 것이기 때문이다.

degree 만큼 회복되는 경우라면 degree의 부호만 반대로 해서 동일한 방법으로 계산해주면 된다.

모든 skill들을 다 반영하고 난 후의 damage_pos 벡터의 상태다. 테두리 안의 부분이 문제에서 유효한 부분이다.

 

데미지 벡터(damage_acc)

데미지 벡터를 구할 때는 2차원 누적합을 이용한다.

(r, c)에는 damage_pos 벡터의 (r, c)의 값에 damage_acc 벡터의 (r-1, c), (r, c-1)에 있는 값을 더하고 (r-1, c-1)에 있는 값을 빼주면 된다. (r-1, c), (r, c-1)의 누적합 부분을 더하게 되면 아래 그림과 같이 (r-1, c-1)의 누적합 부분이 겹치기 때문에 따로 빼주는 것이다.

최종 완성된 damage_acc 벡터의 상태다.

 

board 벡터와 damage_acc 벡터의 각 요소들을 합한 최종 결과는 다음과 같다.

여기서 1 이상인 좌표는 총 10곳이기 때문에 10이 정답이 되는 것이다.

 

 

소스 코드

#include <vector>
using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n=board.size(); int m=board[0].size();
    vector<vector<int>> damage_pos(n+1, vector<int>(m+1, 0)); // 데미지 범위
    vector<vector<int>> damage_acc(n+1, vector<int>(m+1, 0)); // 데미지 누적
    
    for(int i=0;i<skill.size();i++){
        damage_pos[skill[i][1]][skill[i][2]]+=(skill[i][0]==1?-1:1)*skill[i][5];
        damage_pos[skill[i][1]][skill[i][4]+1]+=-1*(skill[i][0]==1?-1:1)*skill[i][5];
        damage_pos[skill[i][3]+1][skill[i][2]]+=-1*(skill[i][0]==1?-1:1)*skill[i][5];
        damage_pos[skill[i][3]+1][skill[i][4]+1]+=(skill[i][0]==1?-1:1)*skill[i][5];
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i!=0) damage_acc[i][j]+=damage_acc[i-1][j];
            if(j!=0) damage_acc[i][j]+=damage_acc[i][j-1];
            if(i!=0&&j!=0) damage_acc[i][j]-=damage_acc[i-1][j-1];
            damage_acc[i][j]+=damage_pos[i][j];
            if(board[i][j]+damage_acc[i][j]>0) answer++;
        }
    }
    return answer;
}

 

정확성, 효율성 모두 통과

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92344