백준[2208] 보석 줍기

아이디어

• Dynamic Programming(동적계획법)을 사용할 줄 안다

풀이

1. 각 자리의 보석까지 m개의 보석을 주울때 총 합을 저장한다.
2. DP를 이용, 이전 DP에서 현재 주울 보석과 각 자리의 m개의 보석만 주웠을 때를 비교해서 큰 값을 저장한다.
   • 왜?
     ex) m이 4일때, 1 2 -999 3 4 5 6 7 이라면, [-999] 이전 무슨 값을 더해도 작아진다, 따라서 다시 m개의 보석을 줍는 것 부터 시작해주어야 한다.
3. 음수 값이 나오면 0을 출력하게끔(아무것도 줍지않고 나옴) 예외처리한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

int arr[100001];
int dp[100001];
int bucket[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    int added = 0;

    for (int i = 1; i <= m; i++) added += arr[i];

    bucket[m] = added;
    dp[m] = added;

    int ans = added;

    for (int i = m + 1; i <= n; i++) {
        bucket[i] = bucket[i-1] - arr[i - m] + arr[i];
    }

    for (int i = m + 1; i <= n; i++) {
        dp[i] = max(dp[i - 1] + arr[i], bucket[i]);
        ans = max(dp[i], ans);
    }

    if (ans < 0) ans = 0;

    cout << ans;

    return 0;
}

평가

조금만 생각하면 금방 풀 수 있는 문제.
골드2로 표시되어 있지만 제 생각에는 실버5? 정도인것 같습니다.
다만, 마지막에 ans < 0 일때를 예외로 처리하는 것을 생각하는데 시간이 조금 걸렸었습니다.