[java] 누적합 알고리즘 ( 백준 - 11659: 구간 합 구하기 4)

누적 합 알고리즘에 대해 알아보자

 

 

누적 합 알고리즘

말 그대로 구간의 누적 합을 구하는 것

정확히는 "수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합"

 

예를 들자면

arr[] = { 1, 2, 3, 4, 5} 가 있다면

arr[0] ~ arr[2] 까지의 누적 합은 1 + 2 + 3 = 6 이다.

 

이 방법은 구간이 작으면 딱히 상관없지만

구간이 100000씩 된다면 그만큼 하나하나 더해줘야 하기 때문에 시간적 소요가 많이 든다.

 

그렇다면 누적합 알고리즘을 적용하면 어떻게 되느냐

배열에 저장을 할 때 합을 해서 더하면 된다

 arr[] = {1, 3, 6, 10, 15} 이런식으로

1번째 부터 3번째 까지의 구간합은

arr[3] - arr[1-1] 과 같다.

 

이것에 대해 좋은 문제가 하나 있다.

 

백준 11659: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

문제

---

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

---

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

 

 

코드

---

시간 제한이 1초이다.

 

누적합 알고리즘을 적용을 안하면 무조건 시간 초과가 날거같다.

그래도 한번 테스트를 해보고싶어 for문으로 작성한 것

 

틀린코드

---

import java.util.*;
import java.io.*;

class Main{
	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];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int sum;
		while(m --> 0) {
			sum = 0;
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int a = x;
			for(int i = 0; i <= y-x; i++) {
				sum += arr[a-1];
				a++;
			}
			if(x == y) {
				sum = arr[x-1];
			}
			System.out.println(sum);
		}
    }
}

 

막 작성했는데 어찌저찌 결과는 잘 나오지만

 

 

시간 초과

 

 

이제 누적합 알고리즘을 적용한 코드로 적용 해보겠다.

 

정답코드

---

import java.util.*;
import java.io.*;

class Main{
	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());
		arr[0] = 0;
		for (int i = 1; i <= n; i++) {
			arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		}
		StringBuilder sb = new StringBuilder();
		while(m --> 0) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			sb.append(arr[y] - arr[x - 1]).append("\n");
		}
		System.out.println(sb);
    }
}

 

 

맞았습니다!!