BOJ 5921 ) Escaping the Farm (C++)

5921번: Escaping the Farm

 소가 20마리밖에 되지 않으므로 모든 경우를 고려해도 된다. DFS를 이용해 각 소를 배에 태울지 말지를 고른 후 N번째 소에 대한 선택까지 끝나면 각 자릿수의 합에서 자리올림이 발생하는지를 검토한다. 

 

#include <iostream>
using namespace std;

int arr[20][9];
int visited[20];
int N, ans;

void dfs(int idx){
    if(idx==N){
        for(int i=0;i<9;i++){
            int sum = 0;
            for(int j=0;j<N;j++){
                if(!visited[j]) continue;
                sum+=arr[j][i]; // i번째 자릿수를 더함
            }
            if(sum>=10) return;
        }
        int cnt =0;
        for(int i=0;i<N;i++){
            if(visited[i]) {
                cnt++;
            }
        }
        ans = max(cnt, ans);
    }
    else {
        visited[idx]=1;
        dfs(idx+1);
        visited[idx]=0;
        dfs(idx+1);
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>N; int num;
    for(int i=0;i<N;i++){
        cin>>num; int j=0;
        while(num>0){
            arr[i][j]=num%10;
            num/=10;
            j++;
        }
    }

    visited[0]=1;
    dfs(0);
    cout<<ans;


    return 0;
}