[BOJ 백준] 구간 합 구하기 4(11659) Java

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

 

문제 설명 : 

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

 

입력 : 

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

 

출력 : 

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

 

제한

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

 

예제 입력 : 

5 3
5 4 3 2 1
1 3
2 4
5 5

 

예제 출력 : 

12

9

1

 

접근법 : 

1) 어떻게 풀 것인가?

N이 총 10만이고, i 부터 j까지 합을 M(100,000) 번 구해야한다.

단순하게 그때 그때 부분합을 구하게 되면 N(10만) * M(10만)으로 시간초과가 예상된다.

 

2가지 방법을 생각해볼 수 있다.

① 인덱스드트리와 같은 자료구조로 특정 구간의 구간합을 저장해서 푸는 방식.

② DP로 DP[i] 는 1부터 i의 누적합이라고 정의한 후, DP[ j ] - DP[i-1] 을 출력하는 방식

 

①의 시간복잡도는 N log N이고

②의 시간복잡도는 N이다.

 

i부터 j까지 숫자가 실시간으로 변한다면 인덱스드트리를 고려해볼만하지만, 

 

문제 조건이 비교적 단순하므로 위에서 간단하게 작성했던

누적합 DP 점화식 : DP[ j ] - DP [ i - 1 ] 로 구현하는 방식으로 풀었다.

자세한 내용은 아래 코드 참고.

 

2) 시간복잡도

N번 입력 받을떄 누적합을 구하므로 O(N)

(Java 기준 -  700ms)

 

3) 공간복잡도

1차원 배열로 가능하므로 특별히 고려하지 않음.

 

4) 풀면서 놓쳤던점

특별히 없음

 

5) 이 문제를 통해 얻어갈 것

DP적 사고방식. 부분의 정답을 모아 전체의 정답을 만들기

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 백준 11659
public class Main {
    
    static int N, M;
    static int start,end; 
    static int [] num, dp;
    static StringBuilder sb;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        num = new int[N+1];
        dp = new int[N+1];
        
        // 1. 입력 받으면서 누적합 구하기
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N;i++){
            num[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i-1] + num[i];
        }
        
        // 2. i ~ j 범위 구간합 구하기
        sb = new StringBuilder();
        for (int i=1; i<=M; i++){
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            sb.append(dp[end]-dp[start-1]+"\n");
            
        }

        // 3. 출력
        bw.write(String.valueOf(sb));
        
        bw.flush();
        bw.close();
        br.close();
    }

}