백준, BOJ, 11659번 C++ [CPP]

이것도 DP의 예로

입력이 많고 테스트 케이스도 많아서

DP 풀어야 하는 방식과 비슷할 거라고 예상하고 들어갔다.

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

---

 

#맞은 풀이

#include<iostream>

using namespace std;

int N,M;
int map[100001];
int dp[100001];

int main(){
    ios :: sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    
    for(int i = 1; i<=N; i++){
        int a;
        cin >> a;
        map[i] = a;
        dp[i] = a+dp[i-1];
    }
    
    while(M--){
        int a,b;
        cin >> a >> b;
        
        cout << dp[b]-dp[a-1] << '\n';
    }
}

 

누적 합을 dp에 저장하는 것이다.

그렇게 되면 10번째까지의 수 빼기 2번째 까지의 수가 3번째부터 10번째 까지의 수가 된다.

 

이런 식이다.

 

그리고 테스트케이스가 많을 땐 항상 아래 코드를 메인에서 실행해줘야한다. 그렇지않으면

맞게 풀어도 시간초과난다.

ios::sync_with_stdio(0);
cin.tie(0);