[백준 JAVA] 11660번: 구간 합 구하기 5

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

 

말 그대로 구간 합을 이용해서 풀어야 하는 문제

 

처음 풀었을땐 그냥 계속 다 더하면서 하면 될꺼 같았는데 그러면 시간초과가 난다.

N = 1024 M = 100,000 일때 시간복잡도는 O(N^2 * M) 이니까 1,000 * 1,000 * 100,000 = 100,000,000,000

약 천억번의 연산이 들어가야 하기 때문이다.

 

따라서 이를 최소 O(N * M) = 100,000,000 안에 해결해야하는데 그러기 위해서는 모든 원소를 일일이 다 더하는게 아니라 미리 더해놔야하는것을 알 수 있다.

 

따라서 누적합을 구하는 방식과 비슷하게 sum[i][j]는 (0, 0) 부터 (i, j) 까지의 구간합을 '미리' 계산해논다.

 

계산하는 방법은 

 

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;

 

이렇게 되는데

 

누적합을 구하는 방법과는 다르게 2차원 배열이므로 [i - 1][j] 값까지의 구간합 + [i][j - 1] 까지의 구간합 - [i - 1][j - 1] 까지의 구간합 + 현재값으로 구하면된다.

 

헷갈린다면 그림판에 직접 색깔을 칠하면서 하면 도움이 된다.

 

[i - 1][j] 값까지의 구간합 + [i][j - 1] 까지의 구간합 + x 를 구하면 [i - 1][j - 1] 까지의 구간합이 겹치므로 한번 빼준다 생각하면 편하다.

 

마지막으로 정답을 구할때도 이를 역순으로 하는것과 비슷한데

 

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

 

즉 x2, y2 까지의 구간합에서 왼쪽상자와 위쪽상자를 빼준뒤 두번뺀 x1 - 1, y1 - 1 이부분을 더해주면 된다.

 

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

public class Main {
    public static int N, M, ans;
    public static int[][] sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        // 1. 입력받기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sum = 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++){
                int x = Integer.parseInt(st.nextToken());
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
            }
        }

        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());

            sb.append(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]).append("\n");
        }

        System.out.println(sb);
    }
}

 

예전에 한번 풀었던 문제여서 거의 바로 풀 수 있었는데 이 개념을 모른다면 떠올리기는 힘들었을꺼같다.

 

이제 GPT의 피드백을 한번 받아봤다.

 

1. long으로 누적합 형 변환
   문제 제약(N≤1024, |Aij|≤1000)에서는 int로도 안전(최대 ≈ 1.048e9)이지만, 습관적으로 long을 쓰면 범용성이 좋아요(유사 문제에서 값 범위가 커질 때 안전).
2. 입출력 미세 튜닝
   StringTokenizer도 충분하지만, 아주 큰 입력에서 살짝 더 빠른 FastReader(BufferedInputStream 기반)를 쓰면 안정적입니다. 현재도 통과엔 문제 없습니다.
3. 전역 변수 최소화/의미 있는 네이밍
   대회 코드에선 지금처럼 전역도 흔하지만, 로컬로 한정하면 테스트/재사용이 용이합니다. sum → ps 같은 이름도 명확해요.
4. 불변 식 캐싱(미미한 최적화)
   루프 안에서 st.nextToken() 4회 대신 int x1=...; 식의 현 구현은 이미 최적에 가깝습니다. 추가로는 없습니다.

long으로 누적합 형 변환은 꼭 필요한 피드백인것같다. 여기까진 생각못하고 얘말대로 항상 습관적으로 int를 쓰는것같다.

 

입출력 미세 튜닝은 아직까지 내 레벨에서는 필요없어보인다.

 

전역으로 굳이 사용안해도 된다는거는 내가 습관적으로 전역변수를 많이 쓰는데 이는 사부님의 가르침이기도 하고 아직까지는 크게 이거때문에 문제가 된적은 없어서 그대로 유지할 꺼 같다.