백준 20167 꿈틀꿈틀 호석 애벌레 - 기능성 혼내주기

 

brute force 문제. 현재 위치에서 먹지 않거나 최소 만족도 이상이 될 때 까지 연속으로 먹은 경우, 이렇게 두 가지에 대해서 최대값을 구해나가면 된다. 먹기 시작하면 무조건 연속으로 먹는다는 것을 유의하자.

 

사실 이 문제는 다음 문제인 꿈틀꿈틀 호석 애벌레 - 효율성 문제를 위한 초석이라 그리 어렵지는 않다. 효율성 문제는 memoization을 추가해도 시간초과가 나서, 나중에 다른 문제를 더 풀어보고 도전할 예정이다.

 

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

int arr[20];
int n, k;

int d(int idx, int sat){
    if(idx == n) return sat > k ? sat-k : 0;

    int ret = d(idx+1, sat);

    for(int i = idx; i < n; ++i){
        sat += arr[i];
        if(sat >= k){
            ret = max(ret, d(i+1, 0) + (sat - k));
            break;
        }
    }

    return ret;
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }

    cout << d(0, 0);
}