2559번: 수열

 

- 문제 사이트: https://www.acmicpc.net/problem/2559

2559번: 수열

 

"11659번: 구간 합 구하기 4"의 확장된 문제이다.

이전 문제가 i 부터 j까지 구간합의 값을 구하는 문제였다면, 이번에는 구간 너비가 주어진 문제이다.

0번부터 i번까지의 누적값을 구한 배열을 이용하여 풀어주도록 한다.

 

1) max 값은 나올 수 있는 가장 작은 값으로 설정: max = (가장 작은 수) * (구간 너비) = -100 * K

2) 구간합을 구하기 위한 배열 생성: sum[N + 1]

3) 누적값을 구하기 위해 배열의 0번값은 0으로 설정: sum[0] = 0

4) i번째에 입력 받은 값 (num)을 이전 누적값에 더해 i번째 누적값으로 저장: sum[i] = sum[i - 1] + num

5) i번째가 K번째에 해당되면 현재 위치에서 K 구간 전에 해당되는 값을 빼 구간 합을 계산: 구간합 = sum[i] - sum[i - K]

6) max 값과 비교하여 큰 값을 max 값으로 저장

 

[예시] N = 5, K = 3인 경우,

index	입력 받는 값 (num)	누적합 배열 (sum[i])	구간 합	max
0	-	0	-	-300
1	3	0 + 3	-	-300
2	-2	(0+3) - 2	-	-300
3	-4	(0+3-2) - 4	sum[3] - sum[0] = (0+3-2-4) - 0 = 3 -2 -4 = -3	-3
4	-9	(0+3-2-4) - 9	sum[4] - sum[1] = (0+3-2-4-9) - (0+3) = -2 -4 -9 = -15	-3
5	1	(0+3-2-4-9) + 1	sum[5] - sum[2] = (0+3-2-4-9+1) - (0+3-2) = -4 -9 +1 = -12	-3

 

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

int main()
{
    int N, K;
    cin >> N >> K;

    long long int sum[N + 1];
    sum[0] = 0;

    long long int num;
    long long int max = -100 * K;
    for (int i = 1; i < N + 1; i++)
    {
        cin >> num;
        sum[i] = sum[i - 1] + num;

        if (i >= K)
        {
            num = sum[i] - sum[i - K];
            max = (max < num ? num : max);
        }
    }
    cout << max;
    return 0;
}

- 메모리: 2676 KB

- 시간: 32 ms

- 코드 길이: 468 B

 

* 연관 문제:

- [백준] 11659번: 구간 합 구하기 4