백준 11659 구간 합 구하기 4(JAVA) - DP(Dynamic Programming)

백준 11659번

 

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

문제설명

첫째 줄에 N(숫자의 개수)과 M(반복할 횟수) 를 입력받아 진행

 

 

접근

처음엔 for문으로 풀어볼까 생각했지만 범위가 각 10만까지라 1초가 넘어 갈것같아 DP로 접근

각 구간까지의 합을 DP 배열에 저장해두고 i,j(구간의 시작과 끝) 을 입력받은 다음 dp[j]에서 dp[i-1]을 빼주면 된다.

(dp[0]은 0을 넣어줌.)

ex) 5 4 3 2 1 을 입력

1. 이를 각 구간까지의 합으로 넣어둔다면 dp[0] = 0, dp[1] = dp[0]+num[1]이 된다. dp[2] = dp[1]+num[2]가 되고 이런식으로 각 배열에 넣어둔다.

2. 만약 1~3 구간의 합을 구해야한다면, dp[3]을 리턴하면 끝. 2~4까지의 구간합을 구해야하면 4까지의 구간합에서 1까지의 합을 빼버리면 되는데 이는 dp[4]-dp[1]이 된다. 이는 dp[j] - dp[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 bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());
        int num[] = new int[N+1];
        int sum[] = new int[N+1];
        tk = new StringTokenizer(bf.readLine());
        for(int i=1;i<=N;i++){
            num[i] = Integer.parseInt(tk.nextToken());
        }
        sum[0] = 0;
        for(int i=1;i<=N;i++){
            sum[i] = sum[i-1]+num[i];
        }

        for(int i=0;i<M;i++){
            tk = new StringTokenizer(bf.readLine());
            int s = Integer.parseInt(tk.nextToken());
            int e = Integer.parseInt(tk.nextToken());
            System.out.println(sum[e]-sum[s-1]);
        }
    }
}