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

1486번 장훈이의 높은 선반

문제 링크

 

해결방법

아주 간단한 DFS 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

• 직원을 탑으로 사용하는 경우
• 직원을 탑으로 사용하지 않는 경우

위와 같은 2가지 경우로 나눠 탐색을 진행한다

만약 전 직원을 탐색했을 때, 탑의 높이가 선반보다 같거나 높다면, 이 중 최소값을 갱신한다

시간복잡도는 전체 직원의 수 20명을 선택하는 경우, 선택하지 않는 경우로 나뉘기 때문에 O(2^20) 을 가지게 된다

 

 

소스코드

문제 해결 시간 : 2h 10m

메모리 : 12636KB

시간 : 9ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;

int testcase;
int n,b,ans;
int a[MAX];

void dfs(int cnt,int height){
    if(cnt == n){
        if(height >= b)
            ans = min(ans,height);
        return;
    }
    
    dfs(cnt+1,height+a[cnt]);
    dfs(cnt+1,height);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        // 입력
        cin >> n >> b;
        
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        
        ans = INF;
        dfs(0,0);
        
        cout << "#" << tc << " " << ans - b << "\n";
    }
    
    return 0;
}