[Java] 11659번: 구간 합 구하기 4 Silver 3

문제 링크

예전에는 DP를 보면 방법이 정말 안 떠올랐고, 막상 풀이를 봐도 벙찌는 느낌이었다.
그래서 차라리 코드라도 작성해볼 수 있는 단순 구현 문제나 어느 정도 풀이가 정해져있는 BFS나 DFS 같은 문제들을 좋아했다.
그치만 지금은 뭔가 넌센스 문제들 같아서 재밌기도 하고, 다른 알고리즘들에 비해서 코드를 많이 작성하지 않아도 돼서 편한 느낌마저 든다.
아마도 DP식의 사고에 익숙하지 않아서 그랬나보다.

이 문제는 거의 2 ~ 3 분만에 풀린 거 같다.
구간합 최적화는 누적합이라는 게 내가 어디서 접해본 적이 있던 건지는 잘 모르겠지만,
뭔가 여기서 손대볼 만한 것들이 거의 없다보니, 아예 처음 접해본 거였다 해도 주어진 배열로 할 수 있는 것을 고민하다 보면 금방 떠올랐을 거 같기도 하고..

어쨋든 누적합 배열을 만들면 된다!

누적합 배열을 미리 구해놓으면 각 배열들은 첫 번째 칸에서 해당 칸까지의 누적합이 된다.
그렇다면 배열 A - 배열 B는 배열 B 다음 칸에서 배열 A 칸까지의 합이 된다.

시간을 좀 더 줄이려면 조금 더 최적화가 가능하다.

1. 입력에서 최적화
   • 입력을 받아서 배열에 값을 저장하지말고, 바로 누적합 배열로 만든다.
2. 출력은 BufferWriter를 사용
   • 출력이 여러 번 해야하므로, BufferWriter를 사용하면 시간 단축이 가능하다.

정답

import java.io.*;
import java.util.*;

public 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));

        // N 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 배열 입력: dp 배열에 누적합으로 바로 저장
        st = new StringTokenizer(br.readLine());
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int input = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + input;
        }


        // 출력
        for (int k = 0; k < M; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int sum = dp[j] - dp[i - 1];
            bw.write(sum + "\n");
        }

        bw.flush();
        bw.close();
    }
}