[백준 20167] 꿈틀꿈틀 호석 애벌레 - 기능성

꿈틀꿈틀 호석 애벌레 - 기능성

이 문제는 오픈톡방에서 유명하신 류호석님이 제출하신 문제입니다.
이 문제는 배열이 30개밖에 되지 않으므로 브루트포스로 풀이가 가능합니다.
풀이 방법은 DFS를 이용하면서 나뭇가지의 먹이를 먹느냐, 먹지 않느냐로 모든 경우의 수를 진행하면 됩니다.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int N, K, mx;
int arr[30];
void DFS(int idx, int eat, int energy){
    if(idx == N){
        mx = max(mx,energy);
        return;
    }
    if(!eat) DFS(idx+1, eat, energy);

    eat += arr[idx];
    if(eat>=K) {
        energy += eat - K;
        eat = 0;
    }
    DFS(idx+1, eat, energy);
}
int main()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> arr[i];
    DFS(0,0,0);
    cout << mx;
}