백준 11659번: 구간 합 구하기 4

 

딱 봐도 단순하게 반복문 돌면서 합 구하면 시간초과로 안될 것 같이 생겼다.

그래도 직접 한번 해봤다.

역시나 오답이다.

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

public class Main {

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int arr[] = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int a = 0; a < m; a++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());

			int sum = 0;
			for (int b = i; b <= j; b++) {
				sum += arr[b];
			}
			sb.append(sum + "\n");
		}

		// 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

 

이 문제의 핵심 포인트는 [i ~ j까지의 합] = [j까지의 합] - [i까지의 합] 이라는 것에 있다.

누적 합을 저장하는 배열을 미리 만들어놓고
미리 계산된 [j까지의 합]과 [i까지의 합]의 차이를 구하면 된다

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

public class Main {

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

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

		// 입력 배열
		int arr[] = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 누적 합 배열
		int[] prefixSum = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			prefixSum[i] = prefixSum[i - 1] + arr[i];
		}

		// [i ~ j까지의 합] = [j까지의 합] - [i까지의 합]
		for (int k = 0; k < m; k++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());

			int sum = prefixSum[j] - prefixSum[i - 1];
			sb.append(sum + "\n");
		}

		// 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}