백준 11659번, 구간 합 구하기 4

백준 11659번 c++ 문제풀이

문제:

백준 11659

풀이:

처음 문제를 봤을 땐 굉장히 단순한 문제라 쉽게 접근해서 그냥 누적 합을 일일이 구하면 풀 줄 알았지만
숫자가 커짐에 따라 시간이 오래거려서 시간 초과가 나고 말았다.
그래서 다른 방식으로 문제에 접근했다.

1. dp로 접근해서, 1부터 n까지의 누적 합을 구해 저장해준다.
2. i부터 j까지의 구간 합을 구하는 것이므로, j까지의 누적합에서 i-1까지의 누적 합을 빼준다. 시간 복잡도 O(1)이다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long dp[100001];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    vector<int> v;

    cin >> n >> m;

    for(int i=0;i<n;i++){
        int a;
        cin >> a;

        v.push_back(a);
    }

    dp[1] = v[0];
    for(int i=2;i<=n;i++){
        dp[i] = dp[i-1] + v[i-1];
    }

    for(int k=0;k<m;k++){
        int i, j;

        cin >> i >> j;

        long long result = 0;
        result = dp[j] - dp[i-1];
        cout << result << "\n";
    }


    return 0;
} 

dp로 접근해도 시간 초과가 난다면,
메인 코드 맨 앞줄에

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

위 코드를 추가하고, endl 대신 “\n” 개행 문자를 써주면 더욱 시간을 단축할 수 있다.

감사합니다.