BOJ : 11659

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

입력받은 배열에서 주어진 구간의 합을 더하는 문제이다.

여기서 간과하면 안되는 점이 제한 시간 1초라는 점이다.

그래서 먼저 구간합을 다 저장해둔 뒤 원하는 구간만큼 빼내서 출력하는 개념으로 가야한다.

 

3. 코드

package week8;

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

public class Q11659_boj {
    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+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++){
            arr[i] = arr[i-1]+Integer.parseInt(st.nextToken());
        }

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

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

        System.out.println(sb);
    }
}

 

4. 시간복잡도

 

O(N)

 

5. 결과

 

 

6. 틀린 이유

 

누적합 배열을 사용하지 않았더니 바로 시간 초과가 났다...