[백준 알고리즘] 백준 11659번 구간 합 구하기 4 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 11659번 구간 합 구하기 4 자바(Java)

1) 문제번호 : 11659번

 

2) 문제 출처

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

2. 문제

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

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- for문을 이용하여 구간합을 구했더니, 시간초과가 떴다.

- 그러면, 배열을 입력받을 때 누적합을 구해서 b의 구간에서 a의 구간을 빼면 구간합이 나온다.

- 배열은 N+1만큼 해서 0자리를 만들어 outOfindex를 없애고, 입력을 받는다.

7. 소스 코드

import java.util.*;

public class Solution {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] arr = new int[N+1];
		
		arr[0] = 0;

		for(int i=1;i<=N;i++) arr[i] = arr[i-1] + sc.nextInt();
		

		
		for(int i=0;i<M;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			System.out.println(arr[b]-arr[a-1]);
		}
	}
}

---