백준 - 구간 합 구하기4

문제 출처:https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

문제 지문을 읽어 보면 간단히 주어진 구간에 덧셈을 진행하면 될 것처럼 보인다. 하지만 N, M, i, j의 범위를 보면 최대 100,000까지 주어질 수 있으므로 시간 초과의 조짐(?)이 보인다.

 

일단 혹시 몰라서 단순히 주어진 구간동안 계속 합치는 연산으로 수행해본 결과.. 예상했던 데로 시간 초과 문제가 발생했다.

결국 i,j의 구간 합을 구한다는 것은 j까지의 구간합에서  i까지의 구간합을 빼면 간단히 구할 수 있다.

애초에 입력받을 때부터 계속 더해주도록 입력을 설정하였다.

 

 

이후 구간을 입력받은 후, 간단히 출력만 해주는 함수를 만들었다.

 

전체 코드

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

public class B11659_구간합구하기4 {
    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 map[] = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            if (i == 0)
                map[i] = Integer.parseInt(st.nextToken());
            else
                map[i] = map[i - 1] + Integer.parseInt(st.nextToken());
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            System.out.println(add(from, to, map));
        }
    }

    private static int add(int from, int to, int[] map) {
        if (from == 0)
            return map[to];
        else
            return map[to] - map[from - 1];
    }
}