백준 11659번 : 구간 합 구하기 4 풀이 (Java) - DP

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

dp 에 익숙하다면 금방 풀 것이다. 10분도 안 걸린듯하다.

Solution

1. N, M 이 모두 최대가 100,000 이다. 만약 합을 구할 구간을 입력받을 때 마다 반복문으로 돌린다고 해도,1~100000 이 100000번 나온다면 100억 회를 해야 한다. 당연히 시간 초과가 뜰 것이다.

2. 즉 이 문제는, N 만큼의 배열의 숫자들을 입력 받을 때, dp 배열에다가 합을 미리 구해놓는 것이다.

dp[N] = 1번부터 N번 까지의 구간 합을 나타내는 것이다. 

3. 그럼 A번 부터 B번 까지 (A <= B) 의 구간 합은,

dp[A] = 1번부터 A번 까지의 구간 합

dp[B] = 1번부터 B번 까지의 구간 합 이므로, dp[B] - dp[A] 이다.

 

Source Code

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

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N,M;
    private static int[] arr, dp;

    private static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        arr = new int[N+1];
        dp = new int[N+1];
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(line.nextToken());
            dp[i] = dp[i-1] + arr[i];
            // 구간합을 구할 때도 매번 i-1 번까지 for문으로 돌릴 필요가 없다.
        }
    }

    private static void solve() throws IOException {
        for(int i = 0; i < M; i++) {
            StringTokenizer section = new StringTokenizer(bufferedReader.readLine());
            int from = Integer.parseInt(section.nextToken()) - 1;
            int to = Integer.parseInt(section.nextToken());
            bufferedWriter.write((dp[to] - dp[from]) + "\n");
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedWriter.close();
        bufferedReader.close();
    }
}