[백준 BOJ/Silver III] 11659번 : 구간 합 구하기 4

 

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

11659번: 구간 합 구하기 4

 

처음에는 단순하게 생각했다

합 구해야하는 구간을 for문 범위에 넣고 구하면되는거 아닌가? 하고 풀었는데 시간 초과,,😮😮

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000

N과 M의 범위가 이렇기 때문에 최대를 생각했을때 N*M이 되고 시간초과가 날 수 밖에 없는 조건이었던거다 누적합을 이용해서 구해야하는 문제였다!!!

입력받은 숫자를 배열에 넣을때 앞에 나온 숫자들을 더하고 쌓아주면서 넣어주면 최종 답을 쉽게 구할 수 있게 된다

 

최종 코드

package BOJ11659;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());

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

//        System.out.println(Arrays.toString(num));

        for(int i = 0 ; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            int answer = num[y] - num[x-1];
            System.out.println(answer);
        }
    }
}