군대에서_코딩하기_알고리즘_11

오랜만에 업로드다.. 사실 이 문제때문에 꽤 애를 먹었는데, 그렇게 어려운 문제는 아니지만 런타임 때문에 자꾸 time limit이 났다..

군대에서 연등시간에 코딩을 한다는 시간적 제약때문에 하루에 기껏해야 한두시간밖에 못한다.. 그것도 이제 온전히 집중하기보다는, 이것저것 하면서 하기 때문에 시간이 좀 걸린것같다.

우선 문제는 간략하게 말하자면, N과 K를 입력받는다. 첫번째 정수 N은 온도를 측정한 전체 날짜의 수이고, K는 합을 구하기 위한 연속적인 날짜의 수이다. 예를들어서, N이 10으로 주어지고, K가 2로 주어진 뒤, 3 -2 -4 -9 0 3 7 13 8 -3 이라는 총 N개(10개)의 수가 주어지면, K가 2이기 때문에, 1 -6 -13 -9 3 10 20 21 5가 되므로, 21을 출력한다.

처음에는 두개의 for문을 이용했다. for문으로 1차원 배열을 처음부터 끝까지 돌면서 동시에, K만큼 온도들을 비교해준후 max값을 뽑아주는 방식을 택했지만, 이렇게하면 N이나 K가 만 단위로 높아졌을 때 tim limit이 뜬다.

그래서 고민을 참 많이 했다. 어떻게하면 for문을 한번만 쓰고 max값을 비교해서 뽑을수 있을까,, 한참을 고민했지만 결국 답을 내지못하고, 강의를 참고했다.
우선 vector라는 개념에 대해 배웠다.

vector <int> list(N)

이라는 형태로 선언을 하는데, 위와 같은 코드는, 크기가 N인 배열 벡터를 선언해준것이다.

이때 왜 벡터를 쓰냐? 라고 물어본다면, 지금까지는 int list[100] 처럼, 우선 공간이 남더라도 넉넉하게 배열을 선언해주었다. 하지만 이렇게 할경우, 공간낭비가 너무 심해서 메모리 낭비가 된다. 따라서 위와같이 벡터를 선언해주면 공간이 자동적으로 입력받은 N개의 크기만큼 할당되기 때문에, 메모리 낭비가 되지 않는다.

따라서 이와같이 vecotr을 선언해서 최소한의 크기만큼 공간을 할당받았다. 그리고 for문을 '한번만' 돌면서, 인덱스 앞의 값은 빼주고 인덱스 뒤에값은 더해주면서, 계속해서 sum값을 최신화하는 동시에, max값을 비교해주었다.
코드는 다음과 같다.

#include<iostream>
#include<vector> 
using namespace std;

int main(){
    
    int N, K, i, max=0, sum=0;
    
    cin>>N;
    cin>>K;
    
    vector <int> list(N);
    
    for(i=0; i<N; i++){
        cin>>list[i];
    }
    
    for(i=0; i<K; i++){
        max = max + list[i];
    }
    sum = max;
   for(i=K; i<N; i++){
       sum = sum +list[i] - list[i-K];
       if(sum>max){
           max = sum;
       }
   }
    
    cout<<max;
}