[백준] 11659번 - 구간 합 구하기 4

 

쉽게 생각해서 for문을 이용하여 결과값을 계산하니 시간초과가 나왔다.

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

public class p11659 {

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

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int[] ary = new int[a];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < b; i++) {
			st = new StringTokenizer(br.readLine());
			int q = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int sum = 0;
			for (int j = q - 1; j < w; j++) {
				sum += ary[j];
			}
			System.out.println(sum);
		}
	}
}

 

그래서 인덱스에 저장할 때 그 값이 아닌 여태까지 인덱스의 값에서 누적해서 더해나가고, 시작하는 인덱스 전 인덱스의 값을 빼주는 방법으로 문제를 해결하였다.

 

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

public class p11659 {

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

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int[] ary = new int[a + 1];
		ary[0] = 0;
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= a; i++) {
			ary[i] = Integer.parseInt(st.nextToken()) + ary[i - 1];
		}

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

			System.out.println(ary[k] - ary[j - 1]);
		}
	}
}