[백준,c++] 24499번 - blobyum

문제

24499번: blobyum

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,K,ans = 0; cin>>N>>K;
    
    vector<int>arr, dp(2*N);
    
    
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        arr.push_back(inp);
    }
    
    for(int i=0; i<N; i++){
        arr.push_back(arr[i]);
    }
    
    dp[0] = arr[0];
    for(int i=1; i<K; i++){
        dp[i]=dp[i-1]+arr[i];
    }
    
    for(int i=K; i<2*N; i++){
        dp[i]=dp[i-1]-arr[i-K]+arr[i];
        ans = max(ans, dp[i]);
    }
    
    cout<<ans;
    
}

 

풀이

이 문제에서 구현하면서 고려해야 할 사항은 두 가지입니다.

• 원형 배열이기 때문에 처리해주어야 한다.
• 입력이 10만까지 들어오기 때문에 O(N)으로 구현해야 한다.

멍청하게도 생각 없이 풀다가 두 번째 사항을 고려하지 못하고 아래와 같이 구현했다가 시간 초과가 떴습니다.

#include <iostream>
#include <vector>

#define ll unsigned long long int
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,K,ans=0; cin>>N>>K;
    vector<int>v;
    
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    
    for(int i=0; i<v.size(); i++){
        int temp = 0;
        for(int k=0; k<K; k++){
            int index = i+k;
            if(i+k>v.size()-1) index = (i+k)%N;
            temp+=v[index];
        }
        ans = max(temp,ans);
    }
    cout<<ans;
    
}

원형 배열 부분을 처리하는 방법은 제가 생각하기에는 두 가지입니다.

1. 위 코드처럼 mod연산을 사용한다.
2. 배열을 처음부터 끝까지 또 추가하여 2*N크기로 만든다.

아래 정답 코드에서는 원형 배열 부분은 2번으로 구현했습니다. 그리고 O(N)으로 구현하기 위해 점화식을 떠올렸는데 풀이과정은 아래와 같습니다.

위 이미지와 같이 dp[i] = dp[i-1] - arr[i - k] + arr[i]; 의 식을 도출해 낼 수 있습니다.