[백준,c++] 18429번 - 근손실

문제

18429번: 근손실

 

코드

#include <iostream>
#include <vector>

using namespace std;


int N, K, ans;
vector<int> v;

bool visited[9];

void dfs(int depth, int power){
    
    if(depth == N-1 && power>=500){
        ans++;
        return;
    }
    
    for(int i=0; i<N; i++){
        if(visited[i]) continue;
        visited[i] = 1;
        if(power - K + v[i] >=500) dfs(depth+1, power - K + v[i]);
        visited[i] = 0;
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>K;
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    
    dfs(0, 500);
    cout<<ans;
    
}

 

풀이

만들어지는 조합의 모든 경우를 탐색하는데, 사전에 현재 운동 키트를 적용했을때 운동 중량이 500미만이 된다면 탐색을 하지 않는 방식으로 구현했습니다.