[JAVA] 백준 11659번 - 구간 합 구하기

 

문제

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

입력

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

출력

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

예제 입력 1 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1

12
9
1

 

나의 풀이

 

i번째에서 j번째 사이 숫자들의 합을 구하는 구간 합 문제이다.

먼저 나는 i번째와 j번째 사이 ( i >= j ) 숫자의 합을 구하기 위해선

i번째까지의 숫자합 sum[i] 에서 j번째 -1 번째까지의 숫자합 sum[j-1] 을 빼면 

i와 j번째 사이 구간합을 구할 수 있을 것이라 생각하고 문제 풀이를 시작했다.

 

i번째와 j번째 사이 구간합 => sum[i] - sum[j-1]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 수의개수 n
		int m = sc.nextInt(); // 합을 구해야하는 개수 m
		int sum[] = new int[n+1];
		sum[0] = 0;
		int array[] = new int[n+1]; 
		
		for(int a = 1; a < n+1; a++) {
			array[a] = sc.nextInt();
			sum[a] = array[a] + sum[a-1];
		}
		
		for (int a = 0; a<m; a++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			System.out.println(sum[j] - sum[i-1]);
		}
	}
}

sum[0]에 0을 삽입하여 j의 값이 1일때 ArrayOutOfBounds가 뜨지 않게 하기 위해 array 배열을 n의 입력값보다 +1 하여

만들었다.

 

array배열에 숫자를 전부 입력받고 다시 for문을 사용하여 sum을 구하기엔 코드도 길어지고 

런타임도 길어질 것 같아서 for문 속 숫자들의 배열인 array 배열에 숫자를 입력 할 때 동시에

a번째 까지의 숫자들의 합을 구하기 위해 sum[a] = array[a] + sum[a-1] 을 해줬다.