[백준 2559] 수열풀기(프썸이를 사용하자)

#1. 조건

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

 

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

#2. 사고 과정

[나의 풀이]

백터를 사용해서 시도했다. 하지만 배열로 사용해도 충분했다. 백터를 사용할 때 문제는 하나씩 순서대로 뽑아낼 수가 없었다. 그래서 방법이 없었다. 

[좀 더 좋은 풀이]

누적합을 사용해서 풀면 쉽다. 누적합을 사용할 때는 누적합을 위한 배열을 따로 만든다. 각 인덱스에는 해당 인덱스까지 더한 값들이 삽입한다. 길이가 5인 배열에서 인덱스 3,4의 합을 구하는거라면 인덱스 4의 값에서 인덱스 3의 값을 빼면 3과 4의 합이 나온다. 누적된 합을 이용해야할 경우에는 누적합 배열을 만들고 사용하면 훨씬 편하다. 

 

#3. 코드

#include<bits/stdc++.h>
using namespace std;

// 조건 식이 틀렸다. -- 생각하기 항상 최대 범위와 최소 범위 생각하기
int fordays, howmanyday, a[100004],psum[100004];

// 누적합 써보기
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
    cin >> fordays >> howmanyday;

    for ( int i = 1; i <= fordays; i++) {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
    int max;
    // 1부터 시작하니깐 이게 맞아.
    for ( int i = howmanyday ; i <= fordays; i++ ){
        if(i == howmanyday){
            max = psum[i];
        }else{
            if(max < psum[i] - psum[i - howmanyday]){
                max = psum[i] - psum[i - howmanyday];
            }
        }
    }
    cout << max;
    
}

#4. 설명

우선 알아 두어야하는 것. 최대값을 구하는 문제일 때는 최소값을 먼저구한다.(ret = min(ret,value)) 최소값을 구하는 문제일 때는 최대값을 먼저구한다. (ret = max(ret,value))

 

그리고 최대값을 비교하는 것이다.