[Java] 11660번: 구간 합 구하기 5 Silver 1

문제 링크

1년 전쯤에 싸피에서 알고리즘 처음 배울 때, 분명히 배웠던 내용이었고, SWEA에서도 풀어봤던 기억이 났었다.

그래서 그냥 바로 코드를 작성했는데, 답이 계속 이상하게 나왔다..

나는 그냥 해당 좌표까지 누적합을 구해놓고, 더 큰 좌표의 값 - 더 작은 좌표의 값을 출력하면 정답이라고 생각했다..

근데 이상한 건 입력 예시 1에서 두 개는 맞고, 한 개는 다르게 나오고 있었다...

왜 그런지 디버깅을 위해서 배열 값을 다 찍어봤는데, 값이 생각했던 것과 다르게 저장돼 있었다..

도중에 DP 배열을 DP[i][j] += dp[i-1][j] + dp[i][j-1] 방식으로도 만들어보고 별 짓을 다 해봤다..

한 시간은 헤맨 거 같은데, 답지를 볼지 말지 정말 고민했다..

근데 1년 전에 분명히 배웠고, 풀기도 했던 문젠데 답지를 까보기에 자존심 상하기도 하고..(1시간쯤 고민했는데도 안 되니까, 내가 다른 비슷한 문제 풀었던 걸 착각하는 건가 싶기도 했다..😂)
바로 풀 수 있겠지라는 생각으로 그림도 안 그리고 했다 보니 마지막으로 그림만 그려보고 그래도 모르겠으면 답지를 보기로 하고 아이패드를 켜서 그림을 그려봤다.

그랬더니.. 웬걸!

(2.2)에서 (3.3)까지의 합을 어떻게 구하는지를 생각해 봤다.

뭔가 그림을 그려보니 예전에 했던 방식이 스멀스멀 기억이 났다.

그래서 검증 차원에서 27 - 6 - 6 + 1를 했더니 16이 딱 나오는 걸 발견했다..!

그래서 그림으로 생각해 보니 왜 그럴 수밖에 없는지를 깨달았다..

뭐 깨달음이라기보다는, 잊고 있었던 걸 다시 기억해 냈다고 해야 할까..

알고리즘은 정말 매일매일 해야 하는구나~..

슬픈 하루다..😢😢

앞으로는 펜과 종이(아이패드)를 꼭 활용하는 습관을 들이도록 하자~..

정답

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

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

        // N, M 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // N*N 배열 입력 받기
        int[][] dp = new int[N + 1][N + 1];
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N + 1; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // dp(누적합)
        // 1. 가로 누적합
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N; j++) {
                dp[i][j + 1] += dp[i][j];
            }
        }

        // 2. 세로 테두리 누적합
        for (int j = 1; j < N + 1; j++) {
            for (int i = 1; i < N; i++) {
                dp[i + 1][j] += dp[i][j];
            }
        }

        // 좌표 입력 받기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken()) - 1;
            int y1 = Integer.parseInt(st.nextToken()) - 1;
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            System.out.println(dp[x2][y2] - dp[x2][y1] - dp[x1][y2] + dp[x1][y1]);
        }
    }
}