🌞 문제

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

🌞 접근법

내구도를 가진 건물이 각 칸 마다 하나씩 있다.
적은 이 건물들을 공격하여 파괴하려 한다.
건물은 적의 공격을 받으면 내구도가 감소하고, 내구도가 0이하가 되면 파괴된다.
반대로, 아군은 회복 스킬을 사용하여 건물의 내구도를 높인다.

공격도 회복도 직사각형 모양으로 사용된다.

파괴된 건물도 회복을 통해서 돌아올 수 있다.

파괴된 건물도 공격을 받으면 내구도가 떨어진다.

조건1. board = 1000 이하, 건물의 개수는 천개
조건2. skill -> 공격또는 회복을 나타내는 구조체이다. type, r1, c1, r2 ,c2, degree의 형태를 가진다.
type 1 -> 공격
type 2 -> 회복
r = 행의 길이
c = 열의 길이
degree는 500이하

위의 상황을 종합적으로 볼 때 skill을 탐색하려면 25만의 시간이 걸린다. 그러기 위해서는 n 시간 안에는 끝내야 될 것으로 보인다.

가장 기본적인 생각에서는 배열을 다 돌면서 해당 배열의 요소에 degree 만큼 더하거나 빼주면 될 것으로 보이나,
이렇게 할 경우 시간복잡도에서 문제가 발생 할 것이다.

결과적으로 모든 skill에 의해서 생성된 데이터가 몇인지만 파악하면 된다.
skill의 길이를 n이라고 둘 때, skill을 n만큼 돌면서 각각의 skill 요소에 범위를 기억하고 있을 규칙을 만들어야 한다.

도무지 방법이 생각이 나지 않아 답안을 확인해봤다.

처음 들어보는 누적합 이라는 것을 알게 됐다.

https://school.programmers.co.kr/questions/25471

🌞 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;


int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
   
    vector<vector<int>> result(board.size()+1,vector<int>(board[0].size()+1,0));
    
    for(int i=0;i<skill.size();i++)
    {
        int x = skill[i][5];
        if(skill[i][0] == 1) x = x*(-1);
        
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        
        result[r1][c1] += x;
        result[r1][c2+1] -= x;
        result[r2+1][c1] -= x;
        result[r2+1][c2+1] += x;
    }
    

    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[0].size();j++)
        {
            result[i][j+1] = result[i][j+1] + result[i][j];
        }
    }
    
    
    
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[0].size();j++)
        {
            result[i+1][j] = result[i+1][j] + result[i][j];
        }
    }
    
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[0].size();j++)
        {
            result[i][j] += board[i][j];
        }
    }
    
    for(int i=0;i<result.size()-1;i++)
    {
        for(int j=0;j<result[0].size()-1;j++)
        {
            if(result[i][j] > 0) answer++;
        }
    }
    
    return answer;
}