[BOJ] 11660. 구간합 구하기 5 (Java)

백준 11660. 구간합 구하기 5 (자바)

11660번: 구간 합 구하기 5

<a1>

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

과 같은 예시를

 

<a2>

1 3 6 10

3 5 15 24

6 15 27 42

10 24 42 64

로 받아가며 저장하면 된다.

 

내가 필요한 현재 셀의 값: 새로 더할 수 + 전 행 같은 열 + 같은 행 전 열 - 전 행 전 열

예) 64(a2-3, 3) = 7(a1-3, 3) + 42(a2-2, 3) + 42(a2-3, 2) - 27(a2-2, 2)

 

근데 이제 인덱스에러 방지를 위해 실제로는

0 0 0 0 0

0 1 3 6 10

0 3 5 15 24

0 6 15 27 42

0 10 24 42 64

이렇게 받음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

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

        int[][] arr = new int[N + 1][N + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n = Integer.parseInt(st.nextToken());
                arr[i + 1][j + 1] = arr[i][j + 1] + arr[i + 1][j] - arr[i][j] + n;
            }

        }

        for (int i = 0; i < M; i++) {   // 테스트케이스
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            System.out.println(arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]);

        }
    }
}

 

---

❌ 틀린 코드

원래 첫 줄이나 첫 행 포함하는 부분을 예외처리로 하려고 했는데 계속 틀려서

첫 행과 첫 열 전체를 0으로 채우고 인덱스에러 발생하지 않게 처리했다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

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

        int[][] arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n =  Integer.parseInt(st.nextToken());
                if (i == 0 && j == 0) {
                    arr[i][j] = n;
                }
                else {
                    if (i == 0) {
                        arr[i][j] = arr[i][j - 1] + n;
                    }
                    else if (j == 0) {   // 첫 줄의 경우
                        arr[i][j] = arr[i - 1][j] + n;
                    } else {
                        arr[i][j] = arr[i-1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + n;
                    }
                }
            }

        }

        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()) - 1;
            int y2 = Integer.parseInt(st.nextToken()) - 1;
            if (x1 == 0 && y1 == 0) {
                System.out.println(arr[x2][y2]);
            } else if (x1 == 0 && x2 == 0) {
                System.out.println(arr[x2][y2] - arr[0][y1 - 1]);
            } else if (y1 == 0 && y2 == 0) {
                System.out.println(arr[x2][y2] - arr[x1 - 1][0]);
            } else if (x1 == 0) {
                System.out.println(arr[x2][y2] - arr[x2][y2 - 1]);
            } else if (y1 == 0) {
                System.out.println(arr[x2][y2] - arr[x2 - 1][y2]);
            } else {
                System.out.println(arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]);

            }
        }
    }
}