[백준/11659][Java] 구간합 구하기

11659번: 구간 합 구하기 4

 

처음에 이중 for문으로 배열을 다 탐색하며 계산을 했으나 시간 초과 발생.
이전에 구한 값을 앞으로 구할 값에 사용 가능 → DP로 구현 가능.

BufferedReader, StringTokenizer, nextToken으로 구현하는 것이 Scanner 쓰는 것 보다 훨씬 빠르다.
후기-> C++이랑 파이썬 쓰다가 자바로 코딩하려니까 적응이 안되는데.. 자바가 생각보다 실행시간도 길고 함수 사용도 복잡해서 적응하는데 시간이 좀 걸릴 것 같다.

원래 배열이 arr이라고 하면, 각 배열의 누적합을 d에 저장한다. (d 배열 하나로도 구현이 가능하다)
해당 배열의 1부터 3번째 배열의 구간합은 d[3]-d[0]을 통해 구할 수 있다.

d[3] = d[2] + arr[3] = d[1] + arr[2] + arr[3] = d[0] + arr[1] + arr[2] + arr[3] = arr[0] + arr[1] + arr[2] + arr[3]

이전에 구한 값들을 사용한다.

package algo0309;

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

public class B11659_구간합구하기 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		int n, m, i, j;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		int[] arr = new int[n+1];
		int[] d = new int[n+1];
		d[0] = 0;
		st = new StringTokenizer(br.readLine());
		for (int t = 1; t <= n; t++) {
			d[t] = d[t - 1] + Integer.parseInt(st.nextToken());
		}
		for (int t = 0; t < m; t++) {
			st = new StringTokenizer(br.readLine());
			i = Integer.parseInt(st.nextToken());
			j = Integer.parseInt(st.nextToken());
			System.out.println(d[j]-d[i-1]);
		}

	}

}​