[백준 2559번] 수열

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

2559번: 수열

풀이) 

아무생각없이 풀면 O(N^2)으로 시간초과가 난다. 투포인터 개념을 이용하여 초기에 배열을 K 사이즈만큼 잡아놓고 범위에 맞춰서 하나씩 빼고 더해주는 방식으로 O(N)으로 해결해야한다.

#include <iostream>
using namespace std;
 
int N, K, s = 0, sum = 0, ans = 0;
int arr[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    for (int i = 0; i < K; i++)
        sum += arr[i];
    ans = sum;
    for (int i = 0; i < N - K; i++)
    {
        sum = sum - arr[i] + arr[i + K];
        ans = sum > ans ? sum : ans;
    }
 
    cout << ans << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!