BOJ 20543 - 폭탄 던지는 태영이
2차원에서 iMos법을 열심히 써서 구현해야 하는 문제이다.
관찰해야 하는 것은 다음과 같다.
항상 어떤 위치 (y,x) 에선 그 위치에 영향을 미칠 수 있는 폭탄의 위치는 1개이다.
예를 들어, (0,0) 위치에 폭탄의 영향이 가해져 있으면 항상 (⌊2M⌋,⌊2M⌋) 위치에 폭탄이 설치가 그만큼 되어있어야 한다.
이것을 imos 법을 해주듯이 구간합 관리를 해주면 풀 수 있다.
이 구현에서 유의해야할 점은 항상 가로먼저 세로먼저 해줘야 한다는 점인데,
가로를 먼저 순회할 때 확인하며 세로는 더하지는 말고 값을 참고만 해서 계산해준다음
어떤 행에 대한 순회가 끝나면 이제 모든 열에 대해 세로 값들을 업데이트 해주는 방식이다.
코드를 봐야 이해할 수 있다.
void solve() {
int N, M;
cin >> N >> M;
vvi b(N + 1, vi(N + 1));
for (int y = 0; y < N; y++)
for (int x = 0; x < N; x++) cin >> b[y][x];
int sum = 0;
for (int y = 0; y < N; y++)
for (int x = 0; x < N; x++) {
b[y][x] *= -1;
sum += b[y][x];
}
int m = M / 2;
vvi ans(N, vi(N)), d(N + 1, vi(N + 1));
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (x) d[y][x] += d[y][x - 1];
b[y][x] += d[y][x];
int bomb = b[y][x] + (y ? d[y - 1][x] : 0);
if (bomb) {
ans[y + m][x + m] += bomb;
d[y][x] -= bomb;
d[y + M][x + M] -= bomb;
d[y][x + M] += bomb;
d[y + M][x] += bomb;
}
cout << ans[y][x] << ' ';
}
if (y > 0) {
for (int x = 0; x < N; x++) {
d[y][x] += d[y - 1][x];
}
}
cout << endl;
}
}
Comments