BOJ 2559 - 수열 / C++

문제 링크 : https://www.acmicpc.net/problem/2559

2559번: 수열

 

 

문제 풀이

처음 생각한 방식은 포인터 2개를 이용해서 0 ~ k / 1 ~ k+1 / 2 ~ k+2 ..를 모두 더해서 최댓값을 구하려고 했다.

하지만 시간초과가 났고 포인터 2개를 더 효율적으로 쓸 수 있는 방식을 찾아보았다.

 

먼저 0 ~ k 를 더한 뒤 0번째 인덱스의 수를 빼고 k+1번째 인덱스의 수를 더하는 방식으로 풀면 시간초과가 나지 않는다.

 

 

소스 코드

시간 초과 코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n, k;
    vector<int> v;
    cin >> n >> k;

    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    int ans = 0;
    int st = 0;
    int en = k;

    for(int i=0; i<n-k; i++){
        int sum = 0;

        for(int i=st; i<en; i++){
            sum += v[i];
        }
        
        ans = max(ans, sum);
        st++;
        en++;
    }

    cout << ans;
}

 

통과 코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n, k;
    vector<int> v;
    cin >> n >> k;

    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    int sum = 0;

    for(int i=0; i<k; i++){
        sum += v[i];
    }
    
    int ans = sum;

    for(int i=0; i<n-k; i++){
        sum -= v[i];
        sum += v[i + k];

        ans = max(ans, sum);
    }

    cout << ans;
}