[백준] 20543번. 폭탄 던지는 태영이(JAVA)

문제

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

---

풀이(1시간)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        long[][] arr = new long[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Long.parseLong(st.nextToken());
            }
        }

        long[][] diff = new long[N + 1][N + 1];
        long[][] answer = new long[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i > 0) {
                    diff[i][j] += diff[i - 1][j];
                }
                if (j > 0) {
                    diff[i][j] += diff[i][j - 1];
                }
                if (i > 0 && j > 0) {
                    diff[i][j] -= diff[i - 1][j - 1];
                }

                long currentVal = diff[i][j];
                long neededChange = arr[i][j] - currentVal;

                if (neededChange != 0) {
                    diff[i][j] += neededChange;
                    if (j + M <= N) {
                        diff[i][j + M] -= neededChange;
                    }
                    if (i + M <= N) {
                        diff[i + M][j] -= neededChange;
                    }
                    if (i + M <= N && j + M <= N) {
                        diff[i + M][j + M] += neededChange;
                    }
                    
                    if (i + M / 2 < N && j + M / 2 < N) {
                        answer[i + M / 2][j + M / 2] += neededChange;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append((-1 * answer[i][j])).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

---

문제 풀이 전략

 

 MxM칸의 좌상단을 기준으로 누적합을 세워가는 것이라는 개념은 잡았다.

만약 이 문제가 누적합으로 잘 와닿지 않는다면 10713번을 풀어보기를 추천한다!

 

누적합이라는 것은 눈치챘지만 2차원 배열에서 구현하는 데 있어 문제가 발생했었다. 

마지막 열에 계속해서 값이 들어가 발생한 문제였다.

최종적으로 모든 반복문을 검사하여 구현에 성공했다.