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

문제 링크

문제 설명

누적합으로 푸는 아주 간단한 실버 문제이다. 하지만 '당연히 되겠지?' 라는 생각으로 반복문을 두번 돌려서 풀다가 시간초과가 발생하는 것을 발견하고 기억하고자 글을 작성했다.😭

정답 코드

풀이는 굉장히 간단하다. i ~ j 까지 합을 구하는 것이기 때문에 n번째까지 더한 값을 담아두는 sum을 선언하고 sum[j] - sum[i-1]을 해서 결과를 출력하면된다.

import java.io.*;  
import java.util.*;  
  
public class Main {  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        String[] firstLine = br.readLine().split(" ");  
        int N = Integer.parseInt(firstLine[0]);  
        int M = Integer.parseInt(firstLine[1]);  
  
        int[] numbers = new int[N + 1];  // 1-based index 사용  
        String[] secondLine = br.readLine().split(" ");  
        for (int i = 1; i <= N; i++) {  
            numbers[i] = Integer.parseInt(secondLine[i - 1]);  
        }  
        int[] sum = new int[N + 1];  
        for (int i = 1; i <= N; i++) {  
            sum[i] = numbers[i] + sum[i - 1];  
        }  
        for (int i = 0; i < M; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int start = Integer.parseInt(st.nextToken());  
            int end = Integer.parseInt(st.nextToken());  
            System.out.println(sum[end] - sum[start - 1]);  
        }  
        br.close();  
    }  
  
}