문제
Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows.
The field can be seen as an N x N grid (1 <= N <= 500), with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any K x K square that is part of the field (1 <= K <= min(N, 25)).
At all times, each cow has a beauty value between 0 and 10^6. The attractiveness index of a picture is the sum of the beauty values of the cows contained in the picture.
The beauty value for every cow starts out as 0, so the attractiveness index of any picture in the beginning is 0.
At Q times (1 <= Q <= 3 * 10^4), the beauty of a single cow will increase by a positive integer due to eating the magical grass that is planted on Farmer John's field.
Farmer John wants to know the maximum attractiveness index of a picture he can take after each of the Q updates.
입력
The first line contains integers N and K.
The following line contains an integer Q.
Each of the following Q lines contains three integers: r, c, and v, which are the row, column, and new beauty value, respectively (1 <= r, c <= N, 1 <= v <= 10^6). It is guaranteed that the new beauty value is greater than the beauty value at that location before.
출력
Output Q lines, corresponding to the maximum attractiveness index of a picture after each update.
풀이
한 칸의 값이 바뀌면 영향을 받는 것은 그 칸을 포함하는 사진들뿐이다. 따라서 전체를 다시 계산하지 않고, 그 범위만 갱신하면 된다.
코드에서는 실제 필드 값은 field에, 각 사진의 합은 photo에 따로 저장한다. 어떤 칸이 diff만큼 바뀌면 그 칸을 포함하는 모든 사진 합에도 diff를 더해 주면 된다.
이후 갱신된 사진 합 중 최댓값을 ans로 유지하면 각 쿼리의 답을 바로 출력할 수 있다. 핵심은 한 점 업데이트가 영향을 주는 사진 범위를 직접 계산하는 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] photo, field;
static int N, K, ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
field = new int[N + 1][N + 1];
photo = new int[N + 1][N + 1];
int Q = Integer.parseInt(br.readLine());
while (Q-- > 0) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
sb.append(solve(r, c, v)).append('\n');
}
System.out.println(sb);
}
static int solve(int r, int c, int v) {
int diff = v - field[r][c];
field[r][c] = v;
for (int i = Math.max(1, r - K + 1); i <= Math.min(N - K + 1, r); i++) {
for (int j = Math.max(1, c - K + 1); j <= Math.min(N - K + 1, c); j++) {
photo[i][j] += diff;
ans = Math.max(ans, photo[i][j]);
}
}
return ans;
}
}복잡도
- 시간 복잡도: 쿼리 하나당 영향을 받는 사진을 최대 개 갱신하므로 이다.
- 공간 복잡도: 원본 필드와 사진 합 배열을 저장하므로 이다.
마무리
한 칸 수정이 어떤 사진들에만 영향을 주는지 정확히 잡으면 전체 재계산이 필요 없어진다. 영향 범위를 직접 순회하며 합을 갱신하는 것이 핵심이다.
