[백준] 2559 수열

백준2559링크

제한시간 1초

입력

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

출력

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

• 풀이방법 1 -> 타임아웃 실패
  이중반복문으로 i번째부터 i+k까지의 온도의 합을 구하기
  n이 커짐에 따라 o(n^2) 시간초과 발생

#include <iostream>
#include<stdio.h>
#include<vector>

using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    
    int max=0;
    
    vector<int> degree;
    
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        degree.push_back(temp);
    }
    
    for(int i=0;i<n-k;i++){
        int sum=degree[i];
        for(int j=i+1;j<i+k;j++){
            sum+=degree[j];
        }
        if(sum>max){
            max=sum;
        }
    }
    
    cout<<max<<endl;
    return 0;
}

• 풀이방법 2
  o(n)으로 풀 수 있는 방법으로 수정
  처음 k일(0 ~ k-1) 동안의 온도의 합 sum을 구하기
  i부터 반복문 돌면서 i의 온도 더하기 & (i-k)일의 온도 빼기
  

#include <iostream>
#include<vector>

using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    
    vector<int> degree;
    
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        degree.push_back(temp);
    }
    
    int max=0,sum=0;
    
    for(int i=0; i < k; i++){ //처음 k일의 온도의 합
        max+=degree[i];
    }
    sum=max;
    
    for(int i=k; i < n; i++){ //i번째 온도 더하기 & i-k번째 온도 빼기
        sum+=degree[i];
        sum-=degree[i-k];
        if(sum>max){
            max=sum;
        }
    }
    
    cout<<max<<endl;
    
    return 0;
}