백준 18429 근손실 - dfs와 백트래킹 (c++)

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

18429번: 근손실

백트래킹을 하면서, 근손실이 나지않는 조건 하에서 dfs를 끝까지 진행한 경우에 결과에 +1씩 해주면 되는 문제였다.

백트래킹의 대표적인 문제로는 n queen 문제가 있다. n queen문제는 체스판에 퀸이 서로를 잡을수 있는 위치에 있을 수 있냐 업냐를 판단하는 함수를 따로 만든 후에 dfs를 진행하면서 백트래킹을 해야한다. 하지만 이 문제는 따로 근손실이 난다 안난다 하는 함수를 굳이 만들 필요없이 500을 넘냐 안넘냐만 판단하면 되기 때문에, n queen보다는 간단한문제인 것 같다.

 

#include <iostream>
using namespace std;
int N,K;
int gain[51];
int answer = 0;
bool visited[51];
int weight = 500;
 
void dfs(int count){
    if(count==N) {
        answer++;
    }
    else{
        for(int i=0; i<N; i++){
            if(!visited[i]){
                visited[i]=true;
                if(weight+gain[i]>=500){
//                    cout<<i;
                    weight += gain[i];
                    dfs(count+1);
                    weight -= gain[i];
                    visited[i]=false;
                }
                else
                    visited[i]=false;
 
            }
        }
    }
}
 
 
int main(void){
    cin>>N>>K;
    for(int i=0; i<N; i++){
        cin>>gain[i];
        gain[i]-=K;
    }
    dfs(0);
    cout<<answer;
 
}