[실버 3] [Java] 백준 11659번: 구간 합 구하기4

아이디어

누적 합 구하기 알고리즘이어서 평소대로 반복문을 사용해서 구했는데 시간 초과가 나왔다.

사실 구간 합 알고리즘을 오늘 처음 알았다.

여러번 합을 구해야 하니 1~n까지의 합을 sum[n]에 저장해 두고

나중에 i ~ j까지의 합이 필요하면 sum[j] - sum[i-1]을 하면 되는거더라

앞으로 알고리즘 생각할 때, 여러번 반복돼서 사용되는 것이 있으면 미리 구해서 저장해버리는 습관을 들여야겠다.

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;

public class N11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        int[] nums = new int[N + 1];
        input = br.readLine().split(" ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(input[i-1]);
        }

        int[] subSums = new int[N + 1];
        subSums[0] = 0;
        for (int i = 1; i <= N; i++) {
            subSums[i] = subSums[i - 1] + nums[i];
        }

        while (M--> 0) {
            input =  br.readLine().split(" ");
            int i = Integer.parseInt(input[0]);
            int j = Integer.parseInt(input[1]);
            int sum = subSums[j] -  subSums[i - 1];
            bw.write(sum + "\n");
        }
        bw.flush();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.