코딩테스트/동적계획법

[누적합] 백준 11659 구간 합 구하기 4 C++

유(YOO) 2022. 2. 9. 12:35

※ 문제

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

 

11659번: 구간 합 구하기 4

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

www.acmicpc.net

 

※ 풀이

dp[i] := 1부터 i까지 배열 합 저장

∴ i부터 j까지의 구간 합 : dp[j] - dp[i] (i <= j)
#include<cstdio>

using namespace std;

int n, m, p, q, sum;
int a[100001];
int dp[100001];

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
        dp[i] = sum; // 1부터 i까지 배열 합 저장
    }

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &p, &q);
        printf("%d\n", dp[q] - dp[p - 1]); (q) 배열 합 - (p-1) 배열 합
    }
}