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

📌 문제

---

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

📌 입력

---

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

📌 출력

---

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

📌 풀이

---

문제를 처음 봤을 때에는 특정 알고리즘 없이 푸는 문제인줄 알았다.
단순히 i와 j를 입력받고 그 구간의 합을 구해서 출력을 해보았다.

1. N과 M을 입력받고 N개의 개수만큼 배열에 넣는다.
2. i와 j를 입력받아 i-1부터 j까지의 합을 구해 출력한다.

수정 전 코드

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());
        StringBuilder sb = new StringBuilder();
        // 첫번째 입력
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 두번째 입력 = 숫자 입력받기
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int i, j;
        for(int k=0; k<M; k++){
            st = new StringTokenizer(br.readLine());
            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());
            int sum = 0;
            for(int l=i-1; l<j; l++)
                sum += arr[l];
            sb.append(sum + "\n");
        }
        System.out.println(sb);
    }
}

그 결과...

시간 초과가 나왔다....

실버3 문제치고 너무 단순하게 생각하기도 했고 M의 값과 i와 j의 차가 클 경우 시간 복잡도가 크게 나올거 같긴 했었다.

그래서 알아보니 부분합 알고리즘이 존재했다.

부분합

O(1)의 시간복잡도를 갖고 원리는 다음과 같다.

1. 저장하려는 개수보다 +1만큼 큰 sum이라는 배열을 선언
2. i=1 부터 N+1보다 작은 동안 sum[i]에 sum[i-1] + 현재 입력받는 값을 저장하여 합들을 저장한다.
3. i부터 j까지의 합을 구할 때 j는 인덱스보다 1이 크기 때문에 sum[j] - sum[i-1]을 통해 구간의 합을 구한다.

이 로직을 이용하여 제출을 하였더니 성공하였다!! 😀😀

📌 최종 코드

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());
        StringBuilder sb = new StringBuilder();
        // 첫번째 입력
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 두번째 입력 = 숫자 입력받기
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());

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


        int i, j;
        for(int k=0; k<M; k++){
            st = new StringTokenizer(br.readLine());
            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());
            sb.append(sum[j]-sum[i-1] + "\n");
        }
        System.out.println(sb);
    }
}

문제 링크 : 11659번: 구간 합 구하기4