[백준 11659] 구간 합 구하기 4 Java 풀이

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

 

접근

수의 개수와 합을 구해야 하는 횟수는 최대 100,000입니다. 구간마다 합을 매번 계산하면 1초안에 모든 구간 합 계산을 끝낼 수 없습니다. 구간 합을 이용하면 시간 복잡도를 O(n)에서 O(1)로 줄여 문제를 해결 할 수 있습니다.

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// 입력 처리
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		// 누적 합
		int[] s = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			s[i] = s[i - 1] + Integer.parseInt(st.nextToken());
		}

		// i번째 수부터 j번째 수까지 합을 구한다.
		for (int k = 1; k <= m; k++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			sb.append(s[j] - s[i - 1]).append("\n");
		}

		// 결과 출력
		System.out.println(sb);
	}
}