[백준] 구간 합 구하기 4 (누적 합, 구간 합, Prefix Sum, 11659번, Java)

q

 

문제설명

입력 & 출력

나의 풀이

이번 문제는 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하는 문제입니다.

for (int i = 0; i < M; i++) {
    int sum = 0;
    token = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(token.nextToken());
    int b = Integer.parseInt(token.nextToken());

    // O(N) 시간이 걸리는 부분
    for (int j = a; j <= b; j++) {
        sum += arr[j-1];
    }
    sb.append(sum).append("\n");
}

 

만약 위와 같이 코드를 작성했다면 각 구간 합을 구하는 데 O(N)의 시간이 걸리기 때문에, 이를 O(1)로 줄이기 위해 누적 합 배열을 사용하는 것이 좋습니다.

---

 

 

먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, StringTokenizer를 사용하여 숫자를 공백을 기준으로 분리하여 저장합니다.

 

그리고 각 수를 저장할 배열 arr을 만들고, 누적 합을 구하기 위하여 prefixSum배열을 N보다 1 크게 초기화를 합니다.

 

각 수를 반복문을 통해서 N개만큼 저장하고, 누적 합 배열에도 각 구간별 누적 합을 저장해 줍니다.

 

그리고 M개의 줄에 걸쳐서 입력을 받고, 각 구간 합을 구하여 StringBuilder에 저장하고 최종적으로 각 구간 합을 출력하여 마무리해 줍니다.

---

 

누적 합과 구간 합에 대한 개념만 알고 있으면 간단하게 풀 수 있는 문제였습니다.

 

누적 합과 구간 합에 대한 자세한 설명은 아래의 참고❗️에서 확인하실 수 있습니다.

 

 

 

 

 

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[Algorithm] 누적 합(Prefix Sum) 알고리즘 알아보기 (Java)