BOJ_11669 : 구간 합 구하기 5

👉 문제링크

11660번: 구간 합 구하기 5

---

---

🔸 문제 분석 🔸

• 2차원 배열의 구간 합을 출력한다.
• 시간초과를 방지하기 위해 구간 합을 미리 계산한다.
  • i = 1일때와 j = 1 는 1차원 배열의 구간 합 채우기 공식이 같다 : sum[i] = sum[i-1] + arr[i]
  • 2차원 배열 구간합 배열을 채우는 공식 : sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + arr[i][j]
    • 구하려는 인덱스의 위쪽과 왼쪽 값을 합하고, 왼쪽 위는 겹치니까 빼준다.
    • 마지막으로 입력된 값을 넣으면 구간 합 배열 준비 완료.
• 입력받은 좌표 범위의 합을 출력한다.
  • x1,y1 부터 x2, y2 범위의 합 : sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1] + sum[x1-1][y1-1]
  • 구간 합에서 값을 구할 범위의 왼쪽줄과 위쪽 줄을 빼주고, 겹치는 왼쪽위 한 칸은 다시 더해준다.

🔸 코드 🔸

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];
        long sum[][] = new long[n+1][n+1];

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

        for (int i = 1; i <= n; i++){ // 구간 합
            for (int j = 1; j <= n; j++){
                sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + arr[i][j];
            }
        }

        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(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]);
        }
    }
}

🔸 코드 해석 🔸

• 입력 값을 저장하는 배열 arr와 구간 합을 저장할 배열 sum의 인덱스는 1~n을 사용한다.
  • i와 j는 1~n
  • 사용하지 않는 0번 인덱스들은 0으로 초기화 되어 있다. (공식을 사용할 때 범위를 벗어나지 않기 위해서)

---

🔸 end 🔸

• 처음엔 1차원 배열 구간 합을 단순 반복하면 시간이 될 줄 알고, 열에만 구간 합을 사용하고 행은 직접 더해주는 식으로 구현했다.
• x와 y를 반대로 사용해서 1회 틀리고, 시간초과가 나는걸 확인한뒤 교재의 풀이를 보며 풀었다.
• 2차원 배열의 구간 합은 정말 생각지 못한 방식이라 좋은 공부가 되었다.