(2022 KAKAO BLIND) 파괴되지 않은 건물
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다. 예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.
첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.
세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.
마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)
최종적으로 총 10개의 건물이 파괴되지 않았습니다.
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.
제한사항
- 1 ≤ board의 행의 길이 (= N) ≤ 1,000
- 1 ≤ board의 열의 길이 (= M) ≤ 1,000
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
- 1 ≤ skill의 행의 길이 ≤ 250,000
- skill의 열의 길이 = 6
- skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
- type은 1 혹은 2입니다.
- type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
- type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
- (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
- 0 ≤ r1 ≤ r2 < board의 행의 길이
- 0 ≤ c1 ≤ c2 < board의 열의 길이
- 1 ≤ degree ≤ 500
- type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
- type이 2이면 degree만큼 건물의 내구도를 높입니다.
- type은 1 혹은 2입니다.
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
문제 풀이
겉보기엔 쉬워보였지만 굉장히 어려운 문제였다. 정확도 테스트는 금방 통과해도 효율성을 아무리 해도 통과할 수 없었는데 2시간 가량 skill배열을 압축하는 것, 범위 단위로 쪼개서 계산하는 것 등등 여러 방법을 생각해보았지만 유효한 것은 하나도 없었다. 결국 해설을 보았는데 ‘누적합’이라는 개념을 알지 못하면 손도 댈 수 없는 문제였다. 코딩테스트는 간혹 이러한 개념을 알지 못하면 풀 확률이 기하급수적으로 낮아지는 문제들이 있어 참 어려운 것 같다.
누적합에 대해 간단히 설명하자면 길이가 4인 배열에서 0부터 2까지 -2를 하고싶다면 길이가 4이고 0으로 초기화된 배열을 새로 만들어서 0에 -2, 2에서 한칸 더 나아간 3에 +2를 해준다. 즉슨
-2 0 0 2
가 된다. 이 상태에서 왼쪽 숫자를 오른쪽에 더하는 누적합 연산을 해주면
-2 -2 -2 0
이 된다. 이 배열을 원래 배열에 더하면 원하는 결과를 얻을 수 있는 것이다. 누적합 계산의 장점은 원하는 변화값을 계속해서 새 배열에 쌓은 뒤 누적합 연산을 마지막에 한번만 해주면 원하는 계산값을 얻을 수 있다는 점이다. 원래는 각 배열의 인덱스마다 계산을 해줘야 하는 것을 기하급수적으로 시간복잡도를 줄일 수 있는 것이다.
2차원 배열에서도 사용이 가능한데 결론만 말하자면 (x1,y1) (x2+1,y2+1)에 +degree, (x1,y2+1) (x2+1,y1) 에 -degree를 넣어주면 된다. 이 방법을 사용하여 문제를 계산하면 효율성 테스트도 통과가 가능하다.
코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
vector<int> v(1001);
vector<vector<int>> b(1001,v); //0으로 초기화된 새 배열
for(vector<int> v : skill) {
if(v[0]==1) v[5]=v[5]-2*v[5];
b[v[1]][v[2]]+=v[5];
b[v[1]][v[4]+1]-=v[5];
b[v[3]+1][v[2]]-=v[5];
b[v[3]+1][v[4]+1]+=v[5]; //필요한 위치에 누적합을 위한 값 대입
}
for(int i=0; i<board.size(); i++) {
for(int j=0; j<board[0].size(); j++) {
b[i][j+1]+=b[i][j]; //왼쪽에서 오른쪽으로 누적합 연산
}
}
for(int i=0; i<board[0].size(); i++) {
for(int j=0; j<board.size(); j++) {
b[j+1][i]+=b[j][i]; //위에서 아래로 누적합 연산
}
}
for(int i=0; i<board.size(); i++) {
for(int j=0; j<board[0].size(); j++) {
board[i][j]+=b[i][j];
if(board[i][j]>=1) answer++;
}
}
return answer;
}