[백준] 구간 합 구하기 4

🔗 문제 보기 - [백준] 구간 합 구하기 4)

📖 문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

✍ 입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

📄 출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    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];  
        st = new StringTokenizer(br.readLine());  
  
        // 반복문을 돌면서 arr 배열에 누적합 계산  
        for(int i = 1; i <= n; i++) {  
            int val = Integer.parseInt(st.nextToken());  
            arr[i] = arr[i - 1] + val;  
        }
        
        for(int i = 0; i < m; i++) {  
            int result = 0;  
  
            st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  
  
            System.out.println(arr[b] - arr[a - 1]);  
        }
    }  
}

🧩 코드풀이

단순히 for문을 이용하여 값을 합하는 식으로 문제를 풀이하게 되면 시간초과가 발생합니다. 따라서 arr배열에 누적합을 계산한 값을 입력하고, O(1) 시간 복잡도로 문제를 풀이해야 합니다.