[JAVA] 백준 11659번: 구간 합 구하기 4

 

---

문제

• 수 N개가 주어졌을 때, i 번째 수부터 j 번째 수까지 합을 구하는 문제.

 

아이디어

• i와 j를 입력 받을 때마다 합을 계산하면 시간초과가 나므로, 미리 1차원 배열에 누적 합을 구해놓고 각 요소의 차를 이용해 해답을 구한다.
• 1, 2, 3, 4, 5, 6이 입력되고, 1과 3이 입력된다고 가정하자.
  • 누적합을 저장할 1차원 배열을 선언한다.
  • 인덱스 1의 위치에 1+2의 결과값을 저장한다.
  • 인덱스 2의 위치에 1+2+3의 결과값을 저장한다.
  • ...
  • 인덱스 5의 위치에 1+2+3+4+5+6의 결과값을 저장한다.
  • 이후 1과 3이 입력되면, 인덱스 2(3-1)에 위치한 값에서(1+2+3) 인덱스 -1(1-2)에 위치한 값을(null) 빼주면 원하던 값을 출력할 수 있다.
  • 이를 식으로 바꾸면 다음과 같다.

$$answer = sum[j-1] - sum[j-2]$$

 

위의 과정을 그림으로 표현한 것

 

풀이

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

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

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

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 초기값으로 초기화
        int[] sum = new int[N];
        sum[0] = arr[0];
        
        // 누적합 계산
        for(int i=1; i<N; i++) {
            sum[i] = sum[i-1] + arr[i];
        }

        int n1 = 0;
        int n2 = 0;
        int result = 0;
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            n1 = Integer.parseInt(st.nextToken());
            n2 = Integer.parseInt(st.nextToken());
            // 인덱스를 벗어난다면, 그대로 n2-1 위치의 요소 출력
            if(n1-2<0) {
                result = sum[n2-1];
            }
            else {
                result = sum[n2-1] - sum[n1-2];
            }
            sb.append(result).append('\n');
        }

        System.out.println(sb);
    }
}

 

 

채점 결과

11659번 채점 결과

 

문제 링크

• 11659번: 구간 합 구하기 4 (acmicpc.net)