[백준] 2559 수열

Posted on | In

오늘은 어쩌다보니 고른 문제가 쉬워서 블로그에다가 포스팅이라도 해야 겠다 싶어서 포스팅하게 되었다! 쉽든 어렵든 꼬박꼬박 공부하면서 포스팅하려고 한다. 오늘과 미래의 나에게 파이팅. 👊🏻

문제 설명

링크 이 문제는 간단한 문제이다! 금방 생각해 낼 수 있는 문제이나, 슬라이딩 윈도우 개념을 설명하기 위해서 가지고 왔다. 슬라이딩 윈도우는 복잡한 기법은 아니고, 그냥 중복되는 요소들을 재사용하는 것이다(메모리 아끼기 용). 따라서 이 문제에서도 슬라이딩 윈도우 기법을 사용해서 메모리를 아끼게 된다. 문제는 간단하다. 주어진 수열의 길이가 n일 때 k 길이의 부분 수열 중에서 합이 가장 커지는 부분을 찾아 합을 return하면 된다.

문제 풀이

간단하다. 그냥 i에서 i+k까지의 합을 구했을 때, i+1에서 i+k+1까지의 합을 구하기 위해서는 i+1~i+k까지의 합에서 i+k+1번째를 더해주고, i번째를 빼주기만 하면 된다. 이런 식으로 s를 갱신하여 슬라이딩 윈도우 기법을 사용할 수 있다. 이렇게 s를 구하면서 max까지 같이 구하면 O(n)에 문제를 풀 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

long long n, k;
int t[100001];

int main(){
    scanf("%lld%lld", &n, &k);
    for(int i=0;i<n;i++) scanf("%d", &t[i]);

    long long sum=0;
    for(int i=0;i<k;i++) sum+=t[i];

    long long max=sum;
    long long s=sum;
    for(int i=k;i<n;i++){
        s=(s+t[i])-t[i-k];
        if(s>max) max=s;
    }
    printf("%lld\n", max);
}