[백준 문제 풀기] 11659번: 구간 합 구하기 4 (DP, 자바)

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

 

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

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

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

 

 

예제 입력, 출력

	예제 입력	예제 출력
1	5 3 5 4 3 2 1 1 3 2 4 5 5	12 9 1

 

사용 알고리즘

DP

 

코드 (자바)

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

// https://www.acmicpc.net/problem/11659
// 구간 합 구하기 4

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		int N = Integer.parseInt(st.nextToken());	// 입력받은 수의 개수
		int M = Integer.parseInt(st.nextToken());	// 합을 구해야 하는 개수
		int[] number = new int[N+1];		// 입력받은 숫자 배열
//		int[][] dp = new int[N+1][N+1];			// 구간 합을 저장할 배열
		int[] dp = new int[N+1];			// 구간 합을 저장할 배열

		st = new StringTokenizer(br.readLine().trim());
		for (int i=1 ; i<=N ; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
		
//		System.out.println(Arrays.toString(number));
		
		
		// 로직 시작
		for (int i=1 ; i<=N ; i++) {
			dp[i] = dp[i-1] + number[i];
		}
		
		// 출력
		for (int i=1 ; i<=M ; i++) {
			st = new StringTokenizer(br.readLine().trim());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
//			System.out.println(dp[from][to]);
			
			System.out.println( dp[to] - dp[from-1]  );
			
		}
		
		
	}
}

/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */