[BOJ 백준] 2559번 : 수열 (C++)

[BOJ 백준] 2559번 : 수열 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 처음 값을 입력받을 때, 연속된 K일만큼 값을 더해서 비교합니다.

2. 현재 연속된 합의 시작 지점과 종료 지점을 저장합니다.

3. 다음으로 연속된 합은 기존에서 시작 지점과 종료 지점을 각각 +1 한 위치입니다.

4. 즉, 다음으로 진행할 때, 현재 시작 지점의 값을 빼고, 다음 종료 지점의 값을 더한 뒤, 비교합니다.

 

과정

수열에 대한 입력값은 모두 -100~100이고, 수열의 크기는 최대 10만입니다.

따라서, 모두 합했을 때, 최댓값은 1000만이므로 int 범위 내에서 처리가 가능합니다.

 

 

예제 2번을 통해서 과정을 자세히 살펴보겠습니다.

 

먼저, 0번째부터 K개를 연속으로 더해서 최댓값으로 처리합니다.

 

시작 위치와 끝 위치를 한 칸씩 뒤로 옮깁니다.

그로 인해, 수열의 0번째 값인 3을 빼고, 수열의 5번째 값인 3을 더합니다.

 

다시 시작 위치와 끝 위치를 한 칸 뒤로 옮깁니다.

그로 인해 수열의 1번째 값인 -2를 빼고, 수열의 6번째 값인 7을 더합니다.

이때, 현재 합(-3)이 기존 최댓값(-12) 보다 크므로 교체합니다.

 

위 과정을 계속해서 반복하겠습니다.

 

 

 

모든 구간을 검사한 뒤, 최댓값인 31을 출력하면 됩니다.

 

 

주의점

문제에서 온도는 -100에서 100 사이의 값을 가진다고 했습니다.

즉, 모두 음수로 구성된 수열이 입력될 수 있으므로, int형에서 가장 작은 음수값을 기준으로 연속된 온도의 값과 비교해야 합니다.

이 점을 놓치고, 0으로 초기화해서 제출하니 34%에서 틀렸습니다..

---

03. 정답 코드

// 실버 3 - 2559번 : 수열
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 날짜 수 N, 연속 K일
    int N, K;
    cin >> N >> K;

    // 온도 입력
    vector<int> tmps(N);
    int start = 0, end = 0;
    int sum = 0;
    int result = numeric_limits<int>::min();

    for(int i = 0; i < N; i++)
    {
        cin >> tmps[i];

        // 처음 연속 K일 온도 합 구하기
        if(end < K)
        {
            end++;
            sum += tmps[i];
        }
    }

    // 처음 연속 K일과 비교
    result = max(result, sum);

    // 시작과 끝의 투 포인터로 옆으로 한 칸씩 계속 밀어서 검사
    while(end < N)
    {
        sum -= tmps[start];
        start++;

        sum += tmps[end];
        end++;

        result = max(result, sum);
    }

    cout << result << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!