(C++) - 백준(BOJ) 20167번 : 꿈틀꿈틀 호석 애벌레 - 기능성

https://www.acmicpc.net/problem/20167

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

brute force로 푼 문제였습니다.

 

📕 풀이방법

 먹이를 선택 또는 선택하지 않는 2가지 경우의 수가 n만큼 발생하기 때문에 n이 20인경우 2^20으로 모든 경우의 수를 확인해도 TLE(시간초과)가 발생하지 않습니다.

📔 입력 및 초기화

 먹이별 에너지를 일차원 배열 energy에 저장합니다.

 

📔 풀이과정

 0번 먹이부터 시작해 선택하지 않는 경우, 여태 먹은 먹이의 누적합이 k를 넘는 경우, k 미만인경우 3가지로 나누어 재귀를 수행합니다.

 

📔 정답출력

 bruteForce함수의 반환값을 출력합니다.

---

📕 Code

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

int bruteForce(int depth, int sum, int num){
    if(depth == n) return num;
    int ret = 0;
    ret = max(ret,bruteForce(depth+1,0,num));

    if(sum + energy[depth] >= k){
        int surplus = (sum + energy[depth]) - k;
        ret = max(ret,bruteForce(depth + 1, 0, num + surplus));
    }

    else ret = max(ret,bruteForce(depth+1, sum + energy[depth] , num));
    return ret;
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> energy[i];
    cout << bruteForce(0,0,0);
}