[코딩테스트] 백준 11660 자바

백준 11660

백준 11660 문제

해당 문제는 시간 제한 1초 안에 주어진 구간의 합을 구해야 한다.

하지만 최악의 경우 n이 1024이고, m이 10만인 경우 2차원 배열은 이중 반복문으로 탐색을 해야 하기 때문에 n2 = 약 100만 * 10만을 해야하기 때문에 시간 제한을 초과하게 된다.

따라서 이번 문제는 O(1) 시간 복잡도로 구간 합을 구할 수 있는 합 배열을 사용한 구간 합을 이용해야 한다.

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

public class Boj11660 {

    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]; // 원본 배열 선언
        int[][] sumArr = new int[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()); // 원본 배열 초기화
                sumArr[i][j] = sumArr[i][j - 1] + sumArr[i - 1][j] - sumArr[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(sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 - 1] + sumArr[x1 - 1][y1 - 1]); // 구간 합 출력
        }
    }
}

풀이

1. n이 최대 1024이면 한 줄이 매우 길어지기 때문에 BufferedReader와 StringTokenizer를 사용한다.
2. n과 m을 입력받고, 0번째 인덱스는 사용하지 않기 때문에 new int[n + 1][n + 1]로 원본 배열 arr와 합 배열 sumArr를 선언한다.
3. 배열을 순환하면서 원본 배열은 입력된 값으로 초기화해주고, 합 배열에는 지금까지 구간의 합으로 초기화 해야하기 때문에 umArr[i][j] = sumArr[i][j - 1] + sumArr[i - 1][j] - sumArr[i - 1][j - 1] + arr[i][j]로 초기화 한다. (현재 구간 합은 지금까지의 인접한 구간 합(왼쪽과 위) - 인접한 구간 합에서의 중복되는 합 + 현재 원본 배열의 값)
4. m만큼 반복하며 좌표값을 입력 받고 sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 - 1] + sumArr[x1 - 1][y1 - 1]로 구간 합을 출력한다. ([x2, y2]는 [0, 0]부터 [x2, y2]까지의 모든 구간의 합이기 때문에 모든 구간 합에서 선택되지 않은 영역의 합을 빼고 중복되는 구간의 합을 더해준다.)