파괴되지 않은 건물 92344

문제

이하생략

접근 방법

차례대로 풀어주는 방법이 있다.

물론 이 방법으론 해결 못 할 것을 알고 있었다.
그렇다고 별다른 방법이 생각나지는 않으니 해설을 찾아봤다.
누적합이라는 것이다.
내가 아는 누적합은 구간의 합을 구할 때 사용하는 것으로 알고 있는데 이것은 조금 변형된 모습이다.

0~5 구간에 2를 더하고 싶다면 차례대로 더하는 방법도 있지만 누적합을 사용하면 이렇다.

2	0	0	0	0	0	-2

구간의 끝에서 한 칸 더 간 곳에 -2를 배치하고 앞부분엔 2를 배치하는 것이다.

2	2	2	2	2	2	0

누적합을 하면 이럴 것이다.
이런 생각이 들 것이다. '기존 방법이란 뭔 차이지?'
이 방법은 숫자가 여러 개일 때 진가를 발휘한다.

2	4	3	0	-4	0	-5

2, 3은 0~5구간에 4는 1~3 구간에 더하고 싶다면 이렇게 표시하면 될 것이다.

2	6	9	9	5	5	0

누적합을 시도하면 별도로 더하는 과정보다 더 적은 연산을 한다.

이것을 2차원에 시도하는 것이다.
0~1, 0~1만큼을 2로 더한다고 생각해보자.

2	0	-2
0	0	0
-2	0	2

누적합을 오른쪽으로 시도한다.

2	2	0
0	0	0
-2	-2	0

밑으로 시도한다.

2	2	0
2	2	0
0	0	0

2차원에서도 정상적으로 되는 것을 확인할 수 있다.
즉 이번 문제에서 요구하는 건 누적합을 하여 시간을 단축하는 것이었다.

코드

#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
    vector<vector<int>> prefixSum(board.size() + 1, vector<int>(board[0].size() + 1));
    int answer = 0;
    for (auto s : skill)
    {
        if (s[0] == 1)
        {
            s[5] *= -1;
        }
        prefixSum[s[1]][s[2]] += s[5];
        prefixSum[s[1]][s[4] + 1] -= s[5];
        prefixSum[s[3] + 1][s[4] + 1] += s[5];
        prefixSum[s[3] + 1][s[2]] -= s[5];
    }
    for (int i = 0; i < prefixSum.size(); ++i)
        for (int j = 1; j < prefixSum[i].size(); ++j)
        {
            prefixSum[i][j] += prefixSum[i][j - 1];
        }
    for (int i = 1; i < prefixSum.size(); ++i)
        for (int j = 0; j < prefixSum[i].size(); ++j)
        {
            prefixSum[i][j] += prefixSum[i - 1][j];
        }
    for (int i = 0; i < board.size(); ++i)
        for (int j = 0; j < board[i].size(); ++j)
        {
            board[i][j] += prefixSum[i][j];
            if (board[i][j] >= 1)
                ++answer;
        }
    return answer;
}

풀이

누적합의 응용과 관련된 문제였다. 건물의 내구도에 더하기 전에 미리 다 더한다는 비슷한 생각은 했어도 스킬의 결과를 구할 때 더하는 것을 한 번에 할 수 있다는 생각은 못 했을 것 같기에 해설을 잘 본 것 같다.