[백준] 구간 합 구하기 5 쉬운 풀이, 여러가지 풀이 java

1. 문제 설명

문제 링크

2. 접근 방식

• sum[i] [j] = (0,0) ~ (i,j) 까지의 합으로 나타냈다.
  i = 0 인 열은 이전 행의 최대 값을 저장하도록 해서, 누적합이 계속 이어지도록 만들었다.
• 하지만 구간 합 (a,b) ~ (c,d)를 구하라 함은, a < x < c , b < y < d 의 인덱스를 가진 배열들의 합을 구하란 말이다. 따라서 단순한 누적 합이 아닌, 배열 안의 네모난 부분을 구해야 한다. 예를 들면

• 그래서 나는 다음과 같이 구했다.

다음과 같이 푸른색 형광펜에서 보라색 형광펜 값을 빼주고 그 결과들을 더 했다.

3. 코드 분석

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 [][] s = new int [N+1][N+1];

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

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int sX = Integer.parseInt(st.nextToken());
            int sY = Integer.parseInt(st.nextToken());
            int eX = Integer.parseInt(st.nextToken());
            int eY = Integer.parseInt(st.nextToken());

            int sum = 0;

            for (int j = sX; j <= eX; j++) {
                sum += (s[j][eY] - s[j][sY-1]);
            }

            sb.append(sum).append("\n");
        }

        System.out.println(sb);
    }
}

(1) 아쉬운 점

구간 합을 구하는데, 반복문이 들어가서 느리다. M^2는 아니지만, 그래서 최악의 경우에는 M*N의 시간복잡도가 든다. N = 1024 이지만, M = 10^5 여서 가까스로 1억 번 연산 안 쪽으로 들어올 것 같다.

4. 성장 하기

해당 문제에서 원하는 구간합이 네모난 배열의 부분을 구하라는 뜻이므로, 그것을 이용하여, 누적 합을 다르게 생각해본다.

푸른색 형광펜이 칠해진 범위까지의 누적합을 생각해보면,
$$
(초록색 형광펜 + 빨간색 형광펜 - 겹치는 부분) + 푸른색 형광펜의 원래 값
$$
이다.
이를 공식으로 표현하면,
$$
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]
$$
이다.
이런 식으로 누적합 또한 (0,0) ~ (i, j) 까지의 네모난 누적 합의 개념으로 바꿔 생각한다. 그러면 누적합 배열의 값은 다음과 같이 채워진다.

이제 여기서 원하는 구간 합을 구하려면 어떻게 해야할까?
만약 (3,3) ~ (4,4) 누적합을 구해야 한다면 다음과 같이 구할 수 있을 것이다. 먼저 일반 배열에서 생각해보자

파란색 부분을 구하려면 전체 누적합 - 초록색 부분 (가로) - 초록색 부분 (세로) + 초록색 겹치는 부분 이다.
이를 누적합에서 보면

빨간색 - (초록색 1 + 초록색 2) + 주황색 이다.
수식으로 표현 하면, ((startX, startY) ~ (endX,endY) 까지의 구간 합 구하기)
$$
sum[endX][endY] - (sum[startX-1][endY] + sum[endX][startY-1])+sum[startX-1][startY-1]
$$
이다.
이를 이제 코드로 구현하면 된다.

5. 다시 풀기

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 [][] 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++) {
                    sum[i][j] = sum[i][j-1] + sum[i-1][j]  - sum[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());

            sb.append((sum[ex][ey] - sum[ex][sy-1] - sum[sx-1][ey] + sum[sx-1][sy-1])).append("\n");
        }
        System.out.println(sb);
    }
}