문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 누적합
시험을 망친 태영이가 인하대학교에 폭탄을 던진다!
인하대학교는 N×N 크기의 정사각형 모양의 땅이다. 인하대학교의 모든 땅은 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 0부터 시작한다.
초기에 인하대학교의 모든 칸은 해발 고도 0미터이다. 하지만 태영이가 폭탄을 던지면 폭발 범위내에 있는 모든 칸의 해발 고도는 1미터씩 줄어들고 폭탄은 그 자리에 남게 된다. 태영이가 던지는 폭탄의 폭발 범위는 폭탄이 던져진 칸을 중심으로 한 M×M 크기의 정사각형 범위이다. M은 홀수이며 폭발 범위의 윗변은 인하대학교의 윗변과 평행하다. 태영이는 폭탄의 폭발 범위가 인하대학교를 넘어가게 던지지 않는다.
태영이가 던진 폭탄들은 한 번만 터지는 것이 아니라 3일 뒤에 한 번 더 터지도록 설계되어있다. 태영이가 폭탄을 던져 모든 폭탄이 첫 번째 폭발을 마무리했을 때의 인하대학교의 해발고도가 주어진다. 각 칸의 해발고도는 H[r][c]이다. 우리가 할 일은 3일 뒤 폭탄이 한 번 더 터지기 전에 모든 칸에 각각 폭탄이 몇 개 있는지 찾아주는 것이다.
입력
양의 정수 N과 M이 공백을 사이에 두고 주어진다.
N개의 줄에 걸쳐 H배열의 값이 주어진다. r번째 줄의 c번째 값은 H[r][c]이다.
출력
N개의 줄에 각각 N개의 정수를 출력한다.
r번째 줄의 c번째 값은 (r, c)에 존재하는 폭탄의 수이다.
제한
- 1 ≤ M ≤ N ≤ 2,000 (M은 홀수)
- 2,147,483,648 ≤ H[r][c] ≤ 0
풀이
모든 칸에 각각 폭탄이 몇 개 있는지 출력해야 한다.
첫 번째 칸 (0, 0)을 봤을 때 만약 해발 고도가 줄어들어 있다면, 폭탄의 영향을 받은 것인데, 그 폭탄의 위치는 (0 + M/2, 0 + M/2)일 수밖에 없다. 왜냐하면 폭탄의 영향이 밖으로 나가지 않기 때문에 (0, 0)칸은 폭탄 영향의 가장 왼쪽이면서, 가장 위쪽이기 때문이다.
두 번째 칸인 (0, 1) 또한 마찬가지다. (0, 0)에서 체크한 폭탄 외에 해발 고도가 더 줄어있다면, (0, 0)에는 미치지 않는 폭탄이 있다는 의미이고, 그 위치는 (0 + M/2, 1 + M/2)가 된다.
모든 칸에 적용되는 패턴이다.
그러면 중요한 건 첫 번째 칸에서 폭탄 위치를 찾고, 영향을 받은 모든 부분을 체크해 줘야 다음 칸에서도 첫 번째 칸과 무관한 폭탄 위치를 찾을 수 있는데,
예를 들어
-1 -2 -2 -1
-1 -2 -2 -1
-1 -2 -2 -1
0 0 0 0
에서 (M은 3임)
첫 번째 칸이 -1이기 때문에
0 0 0 0
0 1 0 0
0 0 0 0로 폭탄의 위치를 찾을 수 있고, 그 영향을 표시하면
-1 -1 -1 0
-1 -1 -1 0
-1 -1 -1 0
이 되며, 이를 통해 두 번째 칸에서 찾아햘 폭탄은 (0, 0)칸에 미치지 않은 -1 영향을 준 폭탄이 되는 것이다.
그런데 이렇게 영향 받은 부분을 매번 표시한다면, 시간초과로 불가능하다.
그래서 이때 누적합을 활용할 수 있다.
폭탄이 영향을 받을 수 있는 부분과 그렇지 않은 부분을 생각해서 필요한 폭탄을 체크해 주는 것이다.
예를 들어
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0에서는 (폭탄이 1행 1열에 하나 있다고 했을 때)
-1 0 0 +1
0 0 0 0
0 0 0 0
+1 0 0 -1
로 표시를 한다. (누적합 배열임)
그리고 칸이 진행됨에 따라 왼쪽에서 오른쪽으로 누적합을 진행하면,
-1 -1 -1 0
0 0 0 0
0 0 0 0
1 1 1 0
이 되는데,
첫 번째 행에서 -1 부분은
실제 map에서 칸이 진행될 때 위에서 값을 가져오기 때문에
결국
-1 -1 -1 0
-1 -1 -1 0
-1 -1 -1 0
-1 -1 -1 0
이 된다.
그런데 폭탄 영향 밖인 4 번째 행은 -1을 가지면 안되기 때문에 누적합이 1로 표시되어있음을 알 수 있다.
그래서 결과적으로 다음과 같이 된다.
-1 -1 -1 0
-1 -1 -1 0
-1 -1 -1 0
0 0 0 0
폭탄 위치를 찾는 과정에서 칸이 진행됨에 따라 누적합도 같이 +하면서 폭탄 위치와 개수를 체크해 나가면 된다.
그래서 폭탄의 영향을 전부 체크하지 않고, 누적합이 활용되었기 때문에 매번 모서리에 해당하는 4 부분만 체크하고, 시간 초과없이 문제를 풀 수 있다.
이 풀이의 시간 복잡도는 O(N^2)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st2.nextToken());
}
}
long[][] prefix = new long[N][N];
long[][] answer = new long[N][N];
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(j != 0) {
prefix[i][j] += prefix[i][j - 1];
}
int uv = 0; //바로 위쪽 값
if(i != 0) {
uv = map[i - 1][j];
}
long need = map[i][j] - (uv + prefix[i][j]);
if(need < 0) {
answer[i + (M/2)][j + (M/2)] = Math.abs(need);
prefix[i][j] += need;
if(j + M < N) {
prefix[i][j + M] -= need;
}
if(i + M < N) {
prefix[i + M][j] -= need;
}
if((i + M < N) && (j + M < N)) {
prefix[i + M][j + M] += need;
}
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
sb.append(answer[i][j]);
if(j != (N - 1)) {
sb.append(" ");
}
}
sb.append("\n");
}
System.out.println(sb.toString().trim());
}
}