본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

[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();
    }

}
반응형