[백준] 11659번 : 구간 합 구하기 4

문제

 

 

접근 방식

Prefix Sum 알고리즘을 사용해 풀 수 있는 문제로

i ~ j까지의 구간합은 (i 까지의 합) - (j-1까지의 합)이라는 공식을 이용해

DP 테이블에는 i까지의 합들을 저장하고 위의 공식대로 계산해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] dp = new int[n + 1];

		st = new StringTokenizer(br.readLine());
		dp[1] = Integer.parseInt(st.nextToken());

		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());

			sb.append(dp[j] - dp[i - 1]).append("\n");
		}

		System.out.println(sb);
	}
}