수열

작성일 | In

[백준] 2559번 - 수열

문제 링크

KOI 2011 초등부 문제.
연속적인 k개의 구간 합 중 최댓값을 구하는 문제이다.
n과 k가 주어지므로, 구간 합 배열(degree)을 만들고 degree[i+k] - degree[i] 를 각 인덱스에 대해 수행 후 최댓값을 비교하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int degree[100001];

int main(void) {
    int n,k;
    scanf("%d %d", &n, &k);

    // 구간 합 비교를 위해 0번째 인덱스를 0으로 초기화
    // 예를 들어, 인덱스 1~2의 구간합을 구하고 싶다면
    // degree[2] - degree[0]으로 구할 수 있다.
    degree[0] = 0;
    for(int i=1; i<=n; ++i) {
        scanf("%d", &degree[i]);
        degree[i] += degree[i-1];
    }
    
    int ans=-100000000;
    for(int i=0; i<=n-k; ++i) {
        int sum = degree[i+k] - degree[i];
        ans = ans < sum ? sum : ans;
    }
    printf("%d", ans);
}
0%