Pr.2559 수열

Pr.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일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입력

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

예제 출력

21

풀이과정

전제조건

1. 시간 복잡도, 공간 복잡도
   • 시간 복잡도 : 이중 for 문을 계산 시, 10만*10만 으로 시간초과 O(10^10)
   • 공간 복잡도 :
2. 최대, 최소 조건
   • 최대 : 10만개의 누적합, 결과값 : 10만 일 * 100
   • 최소 : 1개의 누적합, 결과값 : 10만 일 * -100
3. 사용 알고리즘
   • 누적합 : sum(K) - s[가장 오래된 날] + s[다음 날]
   • max로 비교
4. 반례
   • 모든 값이 음수 일 때 최대값도 음수, 초기화 값보다 작을 수 있다.
   • 1개의 누적합을 구했을 때,

제출 코드

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

int N, K, ret, sum = 0;
int arr[1000004];
int main(){
    cin >> N >> K;

    for(int i = 0; i < K; i++) {
        int a;
        cin >> a;
        arr[i] = a;
        sum += a;
    }
    ret = sum;
    
    for(int i = K; i < N; i++) {
        int a;
        cin >> a;
        arr[i] = a;
        sum = sum - arr[i-K] + arr[i];
        ret = max(ret, sum);
    }
    ret = max(ret, sum);
    cout << ret << '\n';
    return 0;
}

해설

생각해볼 점

- 구간 합 문제 
>  psum[i] = psum[i-1] +a[i]

- 최소/최대 갑 문제
> 최소 일 때 : 최악의 최대 값
> 최대 일 때 : 최악의 최소 값

수정방안

- 구간합을 구한다.
- 구간 합에서 K만큼 뒤에 있는 배열을 뺀다.
> ex) 3, 1, -2, -9, ....에서 </br>
> psum[2] = 0 + 3 + 1 + (-2)
> psum[0] = 0 + 3
> psum[2] - psum[0] => 2개의 연속된 수열의 합 

정답 코드

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

int psum[100004], N, K, ret = -10000004;

int main(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        int temp;
        cin >> temp;
        psum[i] = psum[i-1]+temp;
    }
    
    for (int i = K; i <= N; i++){
        ret = max(ret, psum[i]-psum[i-K]);
    }
    
    cout << ret;
    
    return 0;
}