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

접근

• N이 20까지 이므로, 완전탐색으로 쉽게 풀 수 있었다.

• go(idx,sum,cnt)함수의 매개변수는 각각 현재 먹이 인덱스,만족도,탈피에너지이다. - idx까지 진행했을때 다음단계로의 경우의수는 3가지가 있다.

  1. 현재 먹이를 먹지 않고 그냥 지나가는 경우
  2. 현재 먹이를 먹으면 최소 만족도보다 커지는 경우
  3. 현재 먹이를 먹어도 최소 만족도보다 작은 경우

• 위의 3가지 경우로 재귀함수를 보내주고, idx가 n이라면 그때의 누적 탈피에너지의 값을 현재까지 얻은 값과 비교하여 더 큰 값을 저장하면 된다.

코드(C++)

#include <bits/stdc++.h>
using namespace std;
int n,k,ans,arr[22];

void go(int idx,int sum,int cnt){
    if(idx==n){
        ans = max(ans,cnt);
        return;
    }
    go(idx+1,0,cnt);
    if(sum+arr[idx]>=k) go(idx+1,0,cnt+sum+arr[idx]-k);
    else go(idx+1,sum+arr[idx],cnt);
    return;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>arr[i];
    go(0,0,0);
    cout<<ans;
    return 0;
}

결과