[백준] 11659번 구간 합 구하기 4 (C++) - dynamic programming

문제

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

11659번: 구간 합 구하기 4

코드

#include <iostream>

using namespace std;

int dp[100001];

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m;
  cin >> n >> m;
  for(int i=1; i<=n; i++){
    int a;
    cin >> a;
    dp[i] += dp[i-1]+a;
  }
  for(int k=0; k<m; k++){
    int i, j;
    cin >> i >> j;
    cout << dp[j]-dp[i-1] << '\n';
  }

  return 0;
}

정리

처음에는 이중 for문으로 시도했더니 역시나 시간초과가 나왔다.

문제에 제한이 주어져있으면 웬만해서는 dp로 푸는 문제인 것 같다.

 

그래서 dp로 이 문제를 다시 풀어보았다.

dp배열 안에 각 자리까지의 누적합을 저장한다.

위 예제처럼 5개의 숫자 5, 4, 3, 2, 1이 주어졌다고 해보자.

그러면 dp배열 안에는 [0, 5, 5+4(9), 5+4+3(12), 5+4+3+2(14), 5+4+3+2+1(15)]가 들어간다.

 

여기서 1번째 수부터 3번째 수까지의 합을 구하기 위해서는 어떻게 해야할까?

우리가 구하고 싶은 것은 5+4+3이다.

이것을 구하기 위해서는 5+4+3(12)에서 0을 빼면 된다. → dp[3]-dp[0]

 

2번째 수부터 4번째 수까지의 합을 구하기 위해서는 어떻게 해야할까?

우리가 구하고 싶은 것은 4+3+2이다.

이것을 구하기 위해서는 5+4+3+2(14)에서 5를 빼면 된다. → dp[4]-dp[1]

 

5번째 수부터 5번째 수까지의 합을 구하기 위해서는 어떻게 해야할까?

우리가 구하고 싶은 것은 1이다.

이것을 구하기 위해서는 5+4+3+2+1(15)에서 5+4+3+2(14)를 빼면 된다. dp[5]-dp[4]

 

i번째 수부터 j번째 수까지의 합을 구하기 위해서는 어떻게 해야할까?

위를 토대로 점화식을 구해보면 dp[j]-dp[i-1]이라는 것을 알 수 있다.

 

또한 이 문제는

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

입출력 속도를 높이는 이 코드를 추가해야 문제가 풀린다.

참조