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

1. 문제 설명

문제 링크

2. 접근 방식

해당 문제는 주어지는수의 개수가 10^5 개이다. 이는 n^2만 해도 1억 번의 계산을 넘어서, 시간초과가 날 것이다. 만약 값을 입력 받으면서, 그 전에 받았던 입력들을 일일히 조회하여 구간합을 구한다면, 이는 n^2로 시간 초과가 난다.
누적 합 배열을 이용해 구간 합을 O(1) 안에 구한다.

• sum[] 이라는 배열을 만든다. sum[i]는 sum[0] ~sum[i]까지의 합이다.
  sum[i] = sum[i-1] + arr[i] (현재값) 으로 구할 수 있다.
• i ~ j 까지의 구간합을 구해야할 경우 (i < j) sum[j] - sum[i-1] 하면 된다.

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 [] sum = new int [N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            // 누적합
            if(i == 0){
                sum[i] = Integer.parseInt(st.nextToken());
            }else{
                sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-2;
            int b = Integer.parseInt(st.nextToken())-1;

            sb.append(a < 0? sum[b] : (sum[b]- sum[a])).append("\n");
        }
        System.out.println(sb);
    }
}

* 내 풀이의 아쉬운 점

어짜피 i ~ j의 구간합 = sum[j] - sum[i-1] 이니까, sum[0] = 0으로 하나 비워두고, 진짜 누적합의 출발은 sum[1]부터 했으면, 식이 훨씬 깔끔했으리라 생각이 든다. 왜냐하면, ArrayOutOfBound Exception을 생각하지 않고, 값을 계산해도 되기 때문이다.

4. 성장 하기

sum[0] = 0를 넣어서 진짜 누적합 start는 sum[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];

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start   = Integer.parseInt(st.nextToken());
            int end     = Integer.parseInt(st.nextToken());

            sb.append((sum[end] - sum[start - 1])).append("\n");
        }

        System.out.println(sb);
    }
}