[백준]11659- 구간 합 구하기 4 문제 풀이(Java,자바)

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

 

들어가며

dp의 메모리제이션 기법을 사용하면 쉽게 풀 수 있다.

 

코드

package solved.ac.class3;

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

public class 백준11659_구간합구하기4 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] inputs = reader.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        String[] inputNumbers = reader.readLine().split(" ");
        int[] numbers = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            numbers[i] = Integer.parseInt(inputNumbers[i - 1]);
        }

        int[] dp = new int[100001];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + numbers[i];
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String[] stage = reader.readLine().split(" ");
            int start = Integer.parseInt(stage[0]);
            int end = Integer.parseInt(stage[1]);
            result.append(dp[end] - dp[start - 1]).append("\n");
        }
        System.out.println(result);
    }
}

 

풀이법

dp[n]을 1~n까지의 합을 저장한다.

만약 테스트 케이스처럼 5,4,3,2,1을 입력받았다면

dp[1] =5

dp[2] = 9

dp[3] = 12

dp[4] = 14

dp[5] = 15

 

위와 같은 결과가 나온다.

그러면 문제에서 요구하는 i 번째부터 j번째의 수까지의 합을 어떻게 구할 수 있을까?

 

정답을 미리 말하면 sum(i~j) = dp[i] - dp[j-1] 이다.

 

노가다로 직접 규칙을 찾아보았다.

그렇게 해서 점화식을 도출하였다.

        int[] dp = new int[100001];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + numbers[i];
        }

 

점화식을 작성만 해주면 끝이 난다.