[백준] 🥈 11659 구간 합 구하기 4

📌 난이도

🥈 Silver 3

📌 문제

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

📌 풀이

처음 이 문제를 봤을 때는 너무나도 간단한 문제가 왜 실버3일까? 라는 생각이 절로 들었다.
하지만 막상 이 문제를 풀어보니, 시간초과가 떴다.

하지만 내가 아는 그 어떠한 방법으로도 이 시간초과를 해결할 수가 없었다.
그래서 누적 합(Prefix Sum)이라는 알고리즘에 대해서 공부해보았다.

공부를 해보니까 매우 신박한 방법이었다.
숫자를 받을때, 미리 숫자들을 더해서 누적 합에 대한 배열을 만들어 놓고, 간단하게 start - end를 통해서 여러번의 계산없이 답을 구할 수 있는 알고리즘이었다.
이미 작성한 코드에서 조금만 손을 보니, 매우 빨라진 알고리즘이 나왔다.

이런 알고리즘같은 경우는 쉽지만, 모르면 절대 못푸는 문제이므로 아직도 공부할 것이 많이 남았다는 생각이 드는 문제였다.

📌 Code

package PS;

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

public class N11659_NS {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N + 1];
        arr[0] = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken()) + arr[i - 1];
        }

        int result;
        for (int i = 0; i < M; i++) {
            result = 0;
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            System.out.println(arr[end] - arr[start - 1]);
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁