백준 20543 번 : 폭탄 던지는 태영이 / 2D prefix-sum

문제

• 1 ≤ M​ ≤ N ≤ 2,000 (M은 홀수)
• -2,147,483,648 ≤ H[r][c] ≤ 0

문제 분석

정말 어려운 문제였다. 해결할 아이디어는 문제에서 나온 "폭탄의 폭발 범위가 밖을 넘어가지 않게 한다"라는 조건에서 비롯된 "모서리에 영향을 미치는 칸은 반드시 하나"라는 점이다. 만약에 그렇다면 모서리가 영향을 끼치는 만큼 ( M/2, M/2 )만큼 떨어진 칸에 그만큼의 폭탄이 존재할 것이다. 모서리를 처리하면, 모서리에 인접한 다른 테두리에 영향을 미치는 칸도 하나로 확정되므로 이를 바탕으로 차례대로 폭탄을 처리하면 된다는 것이다. i,j칸의 관점에서 영향을 줄 수 있었던 칸을 모두 처리한다면 칸 i,j에 영향을 미치는 칸은 (i + m/2, j + m/2) 뿐일 것이다.

하지만 이에 대한 문제가 생겼다. 정사각형의 최대 크기가 4 * 10^6인데 하나의 폭탄을 처리하려면 폭발 범위에 있는 모든 칸들을 처리해주는 과정에서 m^2만큼의 복잡도가 필요하기 때문이다.

즉, 이 방식으로 폭탄을 단순하게 처리한다면 O(n^2 *m^2)가 필요하게 되고, 문제의 조건에 의해 이는 시간 초과를 일으킬 것이다.

 

구간 합의 복잡도를 낮춰주는 방식으로 prefix-sum이 존재하는데, 지금까지 풀어온 문제는 1차원 배열의 형태였는데 이를 2차원으로 확장하려니 머리가 깨질뻔 했다.  스터디 당시에는 이해하기 너무 어려워서 걍 고런게 존재하나보다 하고 넘겼는데 DP를 조금 풀어보고 다시 풀어보니 꽤 느낌을 알 수 있었다.  

위와 같이 이미 완성된 것들을 바탕으로 새로운 sum(x,y)를 만들 수 있다. 다시 생각해보면 최대 정사각형의 크기 문제와 유사한 방식이었다. 어쨋든 위와 같은 방식으로 폭탄의 영향을 처리하면 폭탄 처리 복잡도가 상수로 떨어지므로 전체 문제의 복잡도는 대충 O(n^2)이 되서 풀 수 있게된다.

 

2D Prefix-sum 배열을 만들고, 입력과 비교하면 이전에 처리한 폭탄 중 현재 칸에 영향을 주는 폭탄의 갯수를 알 수 있고 잔여 폭탄이 얼마나 있는지 알 수 있다. 우선 원하는 구간의 폭탄의 합을 어떻게 알 수 있는지 다음 그림을 보며 알아보자.

2D Prefix-sum의 정의에 의하여 DP[a][b]는 0,0부터 a,b까지의 구간합이므로, 위와 같은 방식으로 연산하면 원하는 범위의 값을 구할 수 있다.

이제 이 정의를 문제에 적용시켜보자.

현재 점 i,j에 영향을 미치는 폭탄들의 범위는 진하게 색칠된 부분이다. 위 부분의 구간합을 구하고, 현재 점 i,j와 비교해서 만약 잔여 폭탄이 존재한다면 점 (i+m/2, j+m/2)에 폭탄이 존재한다고 판단하고 구간합을 적용시킨다. 왜냐하면 그 외의 범위들은 이미 이전단계에서 모두 처리되었기 때문이다. (모서리부터 시작된 영향을 주는 단 하나의 칸)

이렇게 처리하면된다. 구현만 남았었는데 인덱스의 조건을 맞추기가 꽤나 귀찮았었다.

 

 

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
lld input_map[2002][2002] = {0};
lld DP[2002][2002] = {0};

void solution()
{
    // code
    lld n, m;
    cin >> n >> m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> input_map[i][j];

    if(m == 1)
    {
        for(int i=0; i<n; i++) 
        {
            for(int j=0; j<n; j++)
            {
                cout << -1 * input_map[i][j] << " ";
            }
            cout << endl;
        }
        return ;
    }

    for(int i=0; i<n; i++) 
    {
        for(int j=0; j<n; j++)
        {
            int dp_x = i + m/2 < n ? i + m/2 : n-1;
            int dp_y = j + m/2 < n ? j + m/2 : n-1;
            int dp_x2 = i - m/2 -1 >= 0 ? i - m/2 -1 : 0;
            int dp_y2= j - m/2 - 1 >= 0 ? j - m/2 -1 : 0;

            if(dp_x >= n || dp_y >= n) continue;
            DP[dp_x][dp_y] = DP[dp_x-1][dp_y] + DP[dp_x][dp_y-1] - DP[dp_x-1][dp_y-1];

            lld new_bomb = -1 * ((DP[dp_x][dp_y] - DP[dp_x][dp_y2] - DP[dp_x2][dp_y] + DP[dp_x2][dp_y2]) + input_map[i][j]); 
            DP[dp_x][dp_y] += new_bomb;
        }
    }

    for(int i=0; i<n; i++) 
    {
        for(int j=0; j<n; j++)
        {
            int dp_x = i-1 >= 0 ? i-1 : 0;
            int dp_y = j-1 >= 0 ? j-1 : 0;
            lld new_bomb = DP[i][j] - DP[dp_x][j] - DP[i][dp_y] + DP[dp_x][dp_y];
            cout << new_bomb << " ";
        }
        cout << endl;
    }
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

흠 역시 모르는건 넘기고 나중에 다시보는게 상책인가 싶기도하다.

이해가 안되서 그냥 넘겼던것도 다시보니 풀 수 있던걸 보니 감회가 새로웠었다