(백준) 20543번 - 폭탄 던지는 태영이

##

https://www.acmicpc.net/problem/20543

풀이

static void reset(int x, int y) {
	for (int i = x - m / 2; i <= x + m / 2; i++) {
		for (int j = y - m / 2; j <= y + m / 2; j++) {
			after[i][j] += before[x][y];
		}
	}
}

// ...

for (int i = m / 2; i < n - m / 2; i++) {
	for (int j = m / 2; j < n - m / 2; j++) {
		before[i][j] = -after[i - 1][j - 1];
		reset(i, j);
	}
}

처음에는 폭탄 위치를 찾고, $M \times M$ 배열을 일일이 순회하며 보정해서 TLE이 발생했다. 적절한 폭탄 위치를 찾는 데 $O((N-M)^2)$, 폭탄 영역을 순회하는 데 $O(M^2)$이었기에 전체 시간복잡도는 $O((NM)^2)$이었다.

---

0 0 0 0 0
0 2 0 2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

폭탄이 위와 같이 설치되었다고 하자. 터진 후 고도를 이차원 누적 합으로 구해보자.

-2 0 0 2 0
0 0 0 0 0
-2 0 0 2 0
2 0 0 -2 0
0 0 0 0 0

위와 같은 이차원 누적 합 배열을 만든 후, 왼쪽으로 한 번, 아래쪽으로 한 번 스위핑하면 될 것이다.

배열을 입력받고, 역순으로 스위핑을 수행하여 위 배열을 만든 후 폭탄의 위치를 구했다.

코드

package boj.boj_20543;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int n, m;  
    static long[][] result, tmp1, tmp2, ans;  
  
    public static void main(String[] args) throws IOException {  
  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
  
        String line = br.readLine();  
        StringTokenizer st = new StringTokenizer(line);  
        n = Integer.parseInt(st.nextToken());  
        m = Integer.parseInt(st.nextToken());  
  
        result = new long[n][n];  
        tmp1 = new long[n][n];  
        tmp2 = new long[n][n];  
        ans = new long[n][n];  
  
        for (int i = 0; i < n; i++) {  
            line = br.readLine();  
            st = new StringTokenizer(line);  
            for (int j = 0; j < n; j++) {  
                result[i][j] = Long.parseLong(st.nextToken());  
            }  
        }  
  
        // 이차원 배열 누적 합을 역순으로 진행한다.  
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  
                tmp1[i][j] = result[i][j] - (j > 0 ? result[i][j - 1] : 0);  
            }  
        }  
  
        for (int j = 0; j < n; j++) {  
            for (int i = 0; i < n; i++) {  
                tmp2[i][j] = tmp1[i][j] - (i > 0 ? tmp1[i - 1][j] : 0);  
            }  
        }  
  
        for (int j = 0; j < n; j++) {  
            for (int i = 0; i < n; i++) {  
                System.out.print(tmp2[i][j]);  
            }  
            System.out.println();  
        }  
  
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  
                if (tmp2[i][j] < 0) {  
                    if (i + m / 2 < n && j + m / 2 < n) {  
                        ans[i + m / 2][j + m / 2] = -tmp2[i][j];  
                    }  
  
                    if (i + m < n && j + m < n) tmp2[i + m][j + m] -= tmp2[i][j];  
                    if (i + m < n) tmp2[i + m][j] += tmp2[i][j];  
                    if (j + m < n) tmp2[i][j + m] += tmp2[i][j];  
                }  
            }  
        }  
  
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  
                sb.append(ans[i][j]).append(' ');  
            }  
            sb.append('\n');  
        }  
  
        System.out.println(sb);  
    }  
}

시간복잡도

모든 반복문에서 $N$에 대해 이중 for문을 돌고 있으므로 전체 시간복잡도는 $O(N^2)$이다.

공간복잡도

사용하는 배열이 전부 $N \times N$ 배열이므로 전체 공간복잡도는 $O(N^2)$이다.