[ BOJ / C++ ] 18429번 근손실

이번 문제는 백트레킹을 통해 해결하였다.

• n이라는 사이클동안 키트를 한번씩만 사용할 수 있으므로 사용 여부를 체크하는 bool형의 chk 배열을 선언해준다.
• DFS함수의 인자로 일수를 나타내는 day와 현재 중량을 나타내는 cur을 넣어준다.
• DFS함수 내에서 day와 n이 같을 때, cur이 500보다 크다면 cnt를 증가시켜준다.
• DFS함수 내에서 for문을 0부터 n-1까지 반복하고, 매 반복마다 해당 인덱스의 chk가 false이고, cur-k+kit[i]가 500보다 크거나 같다면 DFS를 재귀호출 해준다.
• 재귀호출 전에 chk[i]를 true로 변경해주고 DFS의 인자로 day+1, cur-k+kit[i]를 넣어 재귀호출한다. 재귀호출 다음 줄에는 모든 경우를 확인해야 하므로 chk[i]를 다시 false로 변경해준다.
• DFS함수가 끝나면 cnt를 출력한다.

#include <iostream>
#define MAX 9
using namespace std;

int n, k;
int kit[MAX];
bool chk[MAX];
int cnt=0;

void Input(){
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>kit[i];
    }
}

void DFS(int day, int cur){
    if(day==n-1){
        if(cur<500){
            return;
        }
        else{
            cnt++;
            return;
        }
    }
    for(int i=0; i<n; i++){
        if(!chk[i]&&cur-k+kit[i]>=500){
            chk[i]=true;
            DFS(day+1, cur-k+kit[i]);
            chk[i]=false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(0, 500);
    cout<<cnt<<endl;
    return 0;
}