[백준] 11659 구간 합 구하기 4

문제

---

처음 내가 푼 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 기본적으로 enter 를 경계로 인식한다.
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); //한 줄에 여러 숫자를 입력 받을 때 사용, 즉 space bar(공백)를 사용할 때

        int n = Integer.parseInt(st.nextToken()); // 첫 줄에 주어지는 숫자
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()); // 두번째 줄에 주어지는 숫자
        int[] arr = new int[n+1]; //를 배열로 담겠다. 0번째 인덱스는 0으로 두고
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k <m; k++) { // 3번째 줄부터 m번 반복한다.
            int sum =0; //합 구하기, 초기화를 위해 for 문 안에 작성
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken()); //i번째 부터
            int j = Integer.parseInt(st.nextToken()); //j번째까지의 합

            for (int l = i; l <= j; l++) {
                sum += arr[l];
            }
            sb.append(sum + "\n");
        }
        System.out.println(sb);
    }
}

주석을 보면 이해할 수 있을 것이다.
처음엔 누적 합이 뭔지 이해하지 않고 생각나는 대로 문제를 풀었다.

단순히 두번째 줄에 주어지는 N개의 숫자들을 배열로 만들고
그 후 주어지는 i,j를 인덱스 값으로 더해서 반환하는 것...

i,j가 주어질 때마다 배열 디벼서 값 더하고 반환하고...
그래서 시간 초과로 문제를 실패한 것 같다.

결과는 똑같이 나오는데 뭐가 문제일까? 하고 찾아보니

---

누적 합 알고리즘을 위한 합 배열

누적 합(구간 합)은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘.
(바로 등장하는 시간 복잡도를 줄이기 위해....)

누적 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의할 수 있다.

// 합 배열 S 정의
S[i] = A[0] + A[1] + ... +A[i-1] +A[i] // A[0]부터 A[i]까지의 합

// 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

// 구간 합을 구하는 공식
S[j] - S[i-1] // i에서 j까지 구간 합
// 밑에서 열심히 머리 굴려서 공식(?) 구했는데 유튜브 강의에 떡하니 나와있는 공식...

그러니까 그냥 단순히 [5,4,3,2,1] 의 배열을 사용해서 i~j의 합을 구하는 것이 아닌
[5,9,12,14,15] 라는 배열을 사용해서 구하라는 소리!

그렇다면 어떻게 i~j의 합을 구할까?

arr[i] = Integer.parseInt(st.nextToken()); // 단순 배열만들기

//(수정) ->

arr[i] = arr[i-1] + Integer.parseInt(st.nextToken()); // 합 배열 만들기

우선 합 배열부터 만들자

그 이후 예제에서 나오는 i=2, j=4 를 기준으로 설명해보자.

위 조건을 단순하게 보면 4 + 3 + 2 = 9를 구하는 것이다.

이것을 합 배열에 적용시키면??

//우선 j=4 이니 arr[4]를 가져오면
arr[4] //14 = 5+4+3+2

//여기서 필요없는 5만 없어지면 딱이다!! 그렇다면 저 5는 어디서 구할까?
arr[1] = 5 //그럼 이 1은 i-1 과 똑같다. 다른 조건에서도 만족할까?


// i=5, j=5 라면?
arr[5] // 15 = 5+4+3+2+1

//여기서 필요없는 5+4+3+2 == 14. 그렇다면??
arr[4] = 14 // i-1 == 4

오케이 코드 작성 드가자

---

해결

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 기본적으로 enter 를 경계로 인식한다.
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); //한 줄에 여러 숫자를 입력 받을 때 사용, 즉 space bar(공백)를 사용할 때

        int n = Integer.parseInt(st.nextToken()); // 첫 줄에 주어지는 숫자
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()); // 두번째 줄에 주어지는 숫자
        int[] arr = new int[n+1]; //를 배열로 담겠다. 0번째 인덱스는 0으로 두고
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k <m; k++) { // 3번째 줄부터 m번 반복한다.
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken()); //i번째 부터
            int j = Integer.parseInt(st.nextToken()); //j번째까지의 합

            int sum = arr[j] - arr[i-1]; // 합 배열 사용. i~j의 합을 구하는 공식
            sb.append(sum + "\n");
        }
        System.out.println(sb);
    }
}

시간이 꽤 걸리긴 했지만 해결은 했다!!
(라고 쓰고 다른 사람들 시간을 봤는데 이정도면 적당히 잘 푼것 같네;;; ㅎㅎ)

오늘의 소득은 누적 합을 구하는 문제는 합 배열을 활용해서 푼다는 것!
관련 문제들을 더 풀어보도록 하자