[BOJ] 11659 - 구간 합 구하기 4

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

난이도: 실버 3

사용언어: JAVA

 

풀이

다이나믹 프로그래밍으로 누적 합을 구하는 아주 기초적인 문제입니다. 배열을 하나 별도로 만들어 우선 해당 값까지의 총합을 구해 저장시켜두고, 입력으로 구간을 받아 해당 구간의 합을 구해주면 됩니다.

 

예제에서 배열의 입력이 5 4 3 2 1 이었으니, 해당 값까지의 합을 구해두는 배열 sum[]은 5 9 12 14 15가 될 것입니다. 여기서 입력으로 시작 위치와 종료 위치를 받아 sum[종료 위치] - sum[시작 위치] + arr[시작 위치]를 계산해서 출력해주면 됩니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N, M;
        int i;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[N]; // 입력을 받는 배열
        int[] sum = new int[N]; // 합을 저장하는 배열
        s = br.readLine();
        st = new StringTokenizer(s);
        for (i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        sum[0] = arr[0]; // sum의 첫 번째 원소 값은 arr의 첫 번째 원소 값과 같다.
        for (i = 1; i < N; i++) {
            sum[i] = arr[i] + sum[i - 1]; // sum 배열을 채워넣어준다.
        }
 
        int first, last;
        for (i = 0; i < M; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            first = Integer.parseInt(st.nextToken()) - 1;
            last = Integer.parseInt(st.nextToken()) - 1;
 
            bw.write(String.valueOf(sum[last] - sum[first] + arr[first]) + "\n"); // 구간합을 구하는 연산 실행
 
        }
 
        bw.flush();
    }
}