75 삐약 : 백준 11659| 구간 합 구하기 4 [바킹독 문제 풀이|DP|JAVA]

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

 

package BKD_0x10_DP;

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

public class BOJ_11659 {
    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[] input = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1;i<=N;i++){
            input[i] = Integer.parseInt(st.nextToken());
        }

        while(M-->0){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int sum=0;
            for(int i=start;i<=end;i++){
                sum += input[i];
            }
            System.out.println(sum);
        }
    }
}

 

 

 

당신도 이렇게 풀었다가 시간 초과 났나요 끼야아아아아악 ><

나만 그런게 아니였다니 끼야아아아아앙ㄱ > O <

 

 

package BKD_0x10_DP;

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

public class BOJ_11659 {
    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[] input = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1;i<=N;i++){
            input[i] = Integer.parseInt(st.nextToken())+input[i-1];
        }

        while(M-->0){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int sum=input[end]-input[start-1];
            System.out.println(sum);
        }
    }
}

 

시간초과가 발생하지 않게 하기 위해서는 누적합을 애초에 배열에 저장하여 이를 활용하면 된다.

배열이 가지고 있는 값은 각 구간까지의 누적합을 뜻한다. 

시작 인덱스와, 끝 인덱스가 제공될 때 해당 구간의 합을 구하는 방법은

끝인덱스가 가지고 있는 값에서 시작인덱스-1에 저장된 값을 빼면 된다.

 

 

 

 

참고 url : https://comain.tistory.com/293

[백준/BOJ] 11659번 : 구간 합 구하기 4 (JAVA / 자바)