[백준_11659번] 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_11659 {
	static int[] dp,arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		arr=new int[n+1];
		dp=new int[n+1];
		
		for(int i=1;i<=n;i++)
			arr[i]=sc.nextInt();
		
		arr[0]=dp[0]=0;
		
		for(int i=1;i<=n;i++)
			dp[i]=arr[i]+dp[i-1];
		
		for(int i=0;i<m;i++) {
			int start=sc.nextInt();
			int end=sc.nextInt();
			
			System.out.println(dp[end]-dp[start-1]);
		}
		
	}

}

 

[고찰]

 이번 문제는 DP로 정답률이 높은 만큼 어렵지 않은 문제였다. 재귀호출 보다는 좀 더 이해하기 쉬운 for문을 사용하여 구간 합을 모두 구해준 후 구간의 시작과 끝을 입력받은 후 dp 값을 빼주는 방식으로 해결하였다.