2022-10-06 algorithm

boj_11659 구간 합 구하기4 - silver 3

Link : 구간 합 구하기4

정보

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 <= N <= 100,000
• 1 <= N <= 100,000
• 1 <= i <= j <= N

예제 입력1

예제 출력1

풀이

1. 처음에는 for문으로 합을 구하면 될 거라 생각했지만 그렇게 한다면 100,000 x 100,000으로 시간 초과가 날 것 같아서 다른 방법을 생각해봤다.
2. 처음부터 숫자를 저장하는 배열과 다른 배열을 만들어서 1인덱스에는 1번까지의 합, 2인덱스에는 2번까지의 합, 3인덱스에는 3번까지의 합... 이렇게 저장을 해두고 나중에 구할 값만 빼주면 될 것이라 생각해서 코드를 구현했다.
3. 예시
   • 5,4,3,2,1 이라는 숫자가 주어진다면 arr = {0,5,4,3,2,1} 담아둔다.
   • int[] dp 배열에는 인덱스까지 합을 더해준다. dp = {0,5,9,12,14,15}
   • 2번째부터 4번째까지의 합을 구한다면
     • 4+3+2 = 5+4+3+2 - 5
     • dp[4] - dp[1] = 9

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n, m;
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i+1] = Integer.parseInt(input[i]);
        }
        dp[1] = arr[1];
        for (int i = 1; i < n; i++) {
            dp[i+1] = arr[i+1]+dp[i];
        }

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            // a-1을 하는 이유는 a번째부터 더해줘야 하기 때문에 a를 빼면 안되기 때문
            int a = Integer.parseInt(input[0])-1;    
            int b = Integer.parseInt(input[1]);

            System.out.println(dp[b]-dp[a]);
        }
    }
}

결과

tags: algorithm, Boj, dp