백준_11659 구간 합 구하기 4(자바) / 누적 합

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

 

잘못된 문제풀이

package com.Back;

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

public class Back_11659 {

	public static void main(String[] args) throws IOException {
		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());
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			hm.put(i, Integer.parseInt(st.nextToken()));
		}
		StringBuilder sb = new StringBuilder();
		for (int k = 0; k < M; k++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int sum = 0;
			for (int i = a; i <= b; i++) {
				sum+=hm.get(i);
			}
			sb.append(sum+"\n");
		}
		System.out.println(sb);
	}
}

기존에는 HashMap을 이용해서 인덱스 값에 값을 넣는 방식을 사용한 뒤에 찾고자 하는 부분을 찾는 작업을 진행했습니다.
But... 시간 초과
찾고자 하는 인덱스에 모두 접근해야한다는 점에서 시간 초과가 발생했습니다. 

 

누적합을 이용한 문제풀이

package com.Back;

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

public class Back_11659 {

	public static void main(String[] args) throws IOException {
		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());
		int[] arr = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i]=arr[i-1]+Integer.parseInt(st.nextToken());
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			sb.append(arr[b]-arr[a-1]+"\n");
		}
		System.out.println(sb);
	}
}

누적합을 이용해서 문제풀이를 진행했습니다.
누적합은 각각의 값을 더한 값을 배열에 저장하는 방식입니다.
원하고자 하는 범위가 3 ~ 6  이면 6번째 까지의 누적 합에서 2번째 까지의 누적 합을 빼주면 쉽게 구할 수 있습니다.