Menu

Subscribe

[JAVA/백준] 11659번: 구간 합 구하기 4

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. n개의 누적합은 변하지 않으므로 한 번만 계산해놓고 필요한 부분을 뽑아서 쓴다.
  2. 입력과 동시에 i까지의 누적합을 구해서 저장한다.
  3. array[j]-array[i-1]을 리턴한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	static int[] array;
	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());
		
		st=new StringTokenizer(br.readLine());
		array=new int[n+1];
		for(int i=1;i<=n;i++) { // i까지의 누적합 구하기
			array[i]=array[i-1]+Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			// a, b사이의 구간합은 array[b]-array[a-1]과 같다
			System.out.println(array[b]-array[a-1]);
		}
	}
	
	
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 누적합 계산은 한 번만 한다
    • n개의 숫자에 따른 합은 변하지 않는 값이므로 한 번만 계산한 후 필요한 부분을 뽑아서 쓴다.
    • array[i]: 0부터 i번째까지의 누적합을 저장한다.
    • 구간 i, j 사이의 합은 array[j]-array[i-1]과 같다.

👏 해결 완료!