백준 11659 구간 합 구하기 4 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간 초과 오류가 났다.

#include <iostream>
using namespace std;

int main(){
    int n, t;
    cin >> n >> t;
    
    int arr[100001];
    for(int i=1; i<=n; i++)
        cin >> arr[i];
    
    int n1, n2;
    for(int i=1; i<=t; i++){
        cin >> n1 >> n2;
        int sum = 0;
        for(int j=n1; j<=n2; j++)
            sum += arr[j];
        cout << sum << "\n";
    }
    
    return 0;
}

 

 

 

시간 복잡도 문제를 해결하기 위해

다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있었다.

최종 코드는 다음과 같다.

ios_base::sync_with_stdio(false);

cout.tie(NULL);
cin.tie(NULL); => 이 3줄을 추가해주어야 빨리 실행된다!!!

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    int n, t;
    cin >> n >> t;
    
    int arr[100001];
    int dp[100001];  //(dp배열의 i번째 값)은 (arr배열의 [1]~[i] 모든 합)임
    
    cin >> arr[1];
    dp[0] = 0;
    dp[1] = arr[1];
    for(int i=2; i<=n; i++){
        cin >> arr[i];        
        dp[i] = dp[i-1] + arr[i];
    }
    
    int n1, n2;
    for(int i=1; i<=t; i++){
        cin >> n1 >> n2;
        cout << dp[n2] - dp[n1-1] << "\n";
    }
    
    return 0;
}