[Java] [백준 11659][누적합] 구간합 4

문제

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

입력

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

출력

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

 

---

 

🌈 풀이 후기

• 전형적인 누적합 문제입니다.누적합 개념을 익히기에 좋은 문제인것 같습니다.

  https://www.youtube.com/watch?v=rI8NRQsAS_s&ab_channel=동빈나

  제가 좋아하는 동빈나에서 자세히 알려주고 있습니다 ㅎㅎ 심심하면 봐보세요!

👩‍🏫 문제 풀이

알고리즘 - 누적합

 

1. 누적합을 배열에 따로 저장해준다.
2. i 와 j의 누적합은 A[j] - A[i-1] 이다. 

package com.Boj.seoul8.week4;

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

// 구간합 
public class BOJ_S3_11659_구간합4 {
	static int N,M;
	static int i,j;
	static int[] A,accum;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		A=new int[N+1];
		accum=new int[N+1];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1;i<=N;i++)
			A[i]=Integer.parseInt(st.nextToken());
		
		int sum=0;
		for(int i=1;i<=N;i++) {
			sum+=A[i];
			accum[i]=sum;
		}
		
		for(int k=0;k<M;k++) {
			st = new StringTokenizer(br.readLine(), " ");
			i=Integer.parseInt(st.nextToken());
			j=Integer.parseInt(st.nextToken());
			int value=accumulate(i,j);
			System.out.println(value);
		}
			
	}
	private static int accumulate(int i,int j) {
		return accum[j]-accum[i-1];
	}

}