[C] 11659: 구간 합 구하기 4

그냥 bruteforce하게 이중 for문을 이용해서 푼다면 시간초과가 나온다.

이때 구간 합을 이용하여야 하는데 i번째까지 합을 dp[i]에 저장하였다가 합을 구해야하는 구간에 대해서

result=dp[b]-dp[a-1];

를 통해 구하면 된다.

 

DP라고 보기에는 애매할 수도 있으나 중복되는 부분 문제를 줄일 수 있다는 점에서 의의가 있는 것 같다.

 

이건 꼭 알아야한다!

구간 합을 이용하면 시간복잡도를 n^2에서 n으로 획기적으로 줄일 수 있다!

 

#include <stdio.h>

int arr[100001];
int dp[100001];

int main(void)
  {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
      {
        scanf("%d",&arr[i]);
      }
    dp[1]=arr[1];
    for(int j=2;j<=n;j++)
      {
        dp[j]=dp[j-1]+arr[j];
      }

    for(int j=1;j<=m;j++)
      {
        int a,b;
        scanf("%d %d",&a,&b);
        int result=dp[b]-dp[a-1];
        printf("%d\n",result);
      }
    
   
  }