백준 11659번: 구간 합 구하기4 [구간합][누적합] -Java

누적합, 구간합 구하기 기본문제.

 

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

11659번: 구간 합 구하기 4

for문돌아서 그때그때 계산하게되면 O(M*N)으로 시간초과 발생. (최악으로 N개까지 다 더해야하니까)

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

728x90

 

<Java코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		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());
		
		st = new StringTokenizer(br.readLine());
		int arr[] = new int[N+1];
		int sum[] = new int[N+1];
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum[i] = sum[i-1]+arr[i]; //구간합 저장 배열, 이전 sum값+현재값
		}
		
		//값 구하기
		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			
			int result = sum[j]- sum[i-1];
			
			System.out.println(result);
		}
		
	}

}

이 알고리즘의 시간 복잡도는 O(N+M) == O(1) == 최대 100,000번 연산