수열

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

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다.

첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다.

두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다.

둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.

이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입/출력 1

10 2
3 -2 -4 -9 0 3 7 13 8 -3

21

예제 입/출력 2

10 5
3 -2 -4 -9 0 3 7 13 8 -3

31

출처

Olympiad > 한국정보올림피아드 > KOI 2011 > 초등부 1번

• 데이터를 추가한 사람: jh05013
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 누적 합
• 두 포인터
• 슬라이딩 윈도우

통과된 코드

슬라이딩 윈도우를 사용하여 누적 합을 구하는 문제

#include <iostream>
using namespace std;

// 최대 100,000개의 샘플 값을 저장할 배열
int Sample[100000] = { 0 };

// 입력될 N과 K, 그리고 결과값을 저장할 변수
int N, K, Res;

int main() {
    ios_base::sync_with_stdio(0); // C++의 표준 스트림의 동기화를 비활성화
    cin.tie(0); // 입력과 출력이 묶이지 않도록 함
    cout.tie(0);

    cin >> N >> K; // N과 K 입력 받기
    for (int i = 0; i < N; i++)
        cin >> Sample[i]; // N개의 샘플 값 입력 받기

    int Start = 0, Sum = 0;
    for (int i = 0; i < K; i++)
        Sum += Sample[i]; // 처음 K개의 값의 합 계산

    Res = Sum; // 처음 K개의 값의 합으로 초기 결과 설정

    // 슬라이딩 윈도우 방식으로 최대 합 계산
    while (Start + K <= N) {
        Res = max(Res, Sum); // 현재까지의 최대 합 갱신
        Sum -= Sample[Start]; // 윈도우의 첫 번째 값 제거
        Sum += Sample[Start + K]; // 윈도우의 마지막 값 추가
        Start++; // 윈도우 시작점 증가
    }

    cout << Res; // 결과 출력
}

범위 지정을 잘못하여 한번 틀렸다.