[백준 알고리즘]11659번: 구간 합 구하기4_Java

[문제]

수 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

​

[예제]

예제 입력1	예제 입력2
5 3 5 4 3 2 1 1 3 2 4 5 5	12 9 1

 

---

>문제 풀이

시간 복잡도를 먼저 살펴보겠습니다.

​

입력 N개에 대한 구간합을 구하려면 O(N)

구간이 M개가 입력되면 O(N*M)

입력되는 N과 M의 범위 1~100,000

그러면 백억...!ㄷㄷ

>>그래서 이렇게 풀면 안됩니다.

​

이 문제를 해결하기 위해 dp를 사용할건데, dp[N+1]배열에 구간합을 저장할 것입니다.

dp[k]= arr[1]~arr[k]까지 저장,

이렇게 되면 i~j까지의 구간합을 구하려면 dp[j]-dp[i-1]을 계산해주면 됩니다.

​

시간복잡도는 한번만 계산해서 저장해놓고 사용하면 되기 때문에 O(N)

​

ex) a~b 구간합을 구한다고 할 때, = dp[b] - dp[a-1];

 

>전체 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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());
		
		//1. 입력
		int N= Integer.parseInt(st.nextToken());
		int M= Integer.parseInt(st.nextToken());
		int[] arr=new int[N+1];
		int[] dp= new int[N+1];
		
		st= new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			arr[i]= Integer.parseInt(st.nextToken()); // arr배열 값을 입력받음과 동시에
			dp[i]=dp[i-1]+arr[i];  // dp[]에 누적합 저장
		}
		
		int a, b;
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			sb.append(dp[b]-dp[a-1]+"\n");
		}
		System.out.println(sb.toString());
	}//main	
}

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

11659번: 구간 합 구하기 4