[SWEA] 1486. 장훈이의 높은 선반

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy

N이 20보다 작으므로 완전 탐색을 사용하여 풀었다.

모든 점원의 키를 선택하는 경우와 선택하지 않는 경우를 모두 구해준다.

그중에서 합이 b이상이면 b와의 차이를 구해 최솟값을 비교한다.

 

#include <cstdio>
using namespace std;
 
int tall[20];
int n,b,min;
 
void solve(int index, int sum) {
 
    //점원의 키를 선택할지 안할지 모두 정했으면
    if(index >= n) {
        //높이가 b 이상이어야 하므로 b보다 작은경우 return
        if(sum < b) return;
 
 
        //차이가 가장 작은 값을 구한다.
        int tmp = sum-b;
 
        //-1(초기값)이거나 기존의 최솟값보다 작은 경우
        if(min == -1 || min > tmp) {
            min = tmp;
        }
        return;
    }
 
 
    //index번째 점원의 키를 더하지 않는 경우
    solve(index+1, sum);
 
    //index번째 점원의 키를 더하는 경우
    solve(index+1, sum+tall[index]);
}
 
 
int main(){
    int T;
    scanf("%d", &T);
    
    
    for(int tc=1; tc<=T; tc++) {
        min = -1;
        scanf("%d %d", &n, & b);
 
        for(int i=0; i<n; i++) {
            scanf("%d", &tall[i]);
        }
 
        solve(0,0);
        printf("#%d %d\n", tc,min);
 
    }
    return 0;
}