백준 11659) 구간 합 구하기 4 Java 자바

문제

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

 

정답

dp를 이용해 풀었고, 처음에 풀 때 시간 복잡도를 계산하지 않고 단순 구현하여 검사를 해보니 시간초과가 계속 떴다..!

....

이런 경우엔 더 좋은 풀이 방법이 있다는 뜻이었고, 내 코드의 문제점은 dp 배열을 함수 내에서 새로 생성하여 dp 배열이 매번 초기화가 되어서 O(j-i)의 시간 복잡도를 가지게 되었다. 

 

누적합을 미리 계산하여 dp 배열에 담은 뒤, j와 i 값을 받아 O(1)로 해결하였다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/11659
public class Main {

    static int N, M, i, j;
    static int[] arr, dp;
    static StringTokenizer st;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N+1];
        dp = new int[N+1];

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

        for (int x = 0 ; x < M; x++){
            st = new StringTokenizer(br.readLine());
            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());
            System.out.println(dp[j]-dp[i-1]);
        }
    }

}