BOJ 20543 - 폭탄 던지는 태영이

BOJ 20543 - 폭탄 던지는 태영이

2차원에서 iMos법을 열심히 써서 구현해야 하는 문제이다.

관찰해야 하는 것은 다음과 같다.

항상 어떤 위치 $(y,x)$ 에선 그 위치에 영향을 미칠 수 있는 폭탄의 위치는 1개이다.

예를 들어, $(0, 0)$ 위치에 폭탄의 영향이 가해져 있으면 항상 $(\left\lfloor \dfrac M2 \right\rfloor, \left\lfloor \dfrac M2 \right\rfloor)$ 위치에 폭탄이 설치가 그만큼 되어있어야 한다.

이것을 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;
   }
}