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

 

11659번: 구간 합 구하기 4

문제

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i  ≤ j ≤ N

---

문제는 매우 간단하다. 하지만 중요한 건 제한조건이다 

N과 M의 최대가 100,000 십만이다

이문제를 이중 for문으로 푼다면 10,000,000,000 백억 즉 시간복잡도가 100억이 나온다

하지만 평균적으로 컴퓨터 cpu 연산속도가 1초에 1억 정도 나오니깐 이 문제를 풀라면 100초가 걸린다는 것이다.. 무조건 시간초과다

 

이문제를 해결하기 위해 prefix sum 알고리즘 즉 누적합을 통하여 문제를 풀었다

 

N개의 값을 입력할 때 이 값은 변하지 않은 불변값이다 이걸 그대로 쓰지 않고

누적합을 사용해 배열에 저장을 할 것이다 누적합은 말 그대로 누적해온 값을 더하는 것으로

첫 번째 값은 그대로 넣어주고 두 번째 값부턴 첫 번째 값부터 더한 값을 더해주는 것이다

그 후 start에서 end까지의 합을 알고 싶다면 arr [end]-arr [start-1] 값을 구해주면 답이 나온다!

이렇게 풀어주면 시간복잡도 O(N)으로 초과 없이 잘 풀 수 있다!

 

---

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

public class BJ_CT_13 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        st=new StringTokenizer(br.readLine());
        arr[1]=Integer.parseInt(st.nextToken());
        for(int i=2;i<=N;i++){
            arr[i]=arr[i-1]+Integer.parseInt(st.nextToken()); //누적합 배열을 만들어줌
        }
        // 5 9 12 14 15
        for(int i=0;i<M;i++){
            st=new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            bw.write((arr[end]-arr[start-1])+"\n");
        }

        bw.flush();

    }
}

입출력에서 BufferedReader와 BufferedWriter를 써준 건 입출력이 가장 빠르기 때문이다

그 후 bw.write를 통해 값들의 출력을 저장해 두고 bw.flush()를 사용해 데이터의 값들을 모두 출력시켜 준다!

처음엔 BufferedWriter 사용하지않고 배열에 담아 출력을 했는데 그땐 

통과는 했지만 시간이 1388ms 걸렸다면

BufferedWriter 사용했을땐 시간이 거의 반이 줄은걸 볼 수 있다.. 이렇게 사용되는 메서드들의 시간복잡도를 잘 알아야

시간을 줄일 수 있댜.. 

시간복잡도중요성을 많이 알게 된 문제였다! 그래서 실버 3인 듯!

아무튼 통과!