[백준] Escaping the Farm

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

5921번: Escaping the Farm

문제부터 간단하게 요약하면,

 

소들이 농장을 탈출하는데, 소들은 무게를 가집니다. 이 때, 소들은 바보라 소들의 무게를 더했을 때, 올림이 생기는 경우 배가 침몰한다고 생각해서 탈수 없다고 합니다. 즉 더했을 때, 올림이 생기지 않을 만큼만 소들만 배를 탄다고 합니다. 이 때, 탈출 가능한 최대 소의 마릿수를 구해야 하는 문제입니다.

 

실제로 문제를 한번 읽어보는 것을 추천합니다.

 

<Solution>

10이상이 되어 올림이 생기는 경우, true 아닌경우 false를 return하는 carry_happen 함수를 만들고, DFS를 통해 탐색하면 됩니다.

 

이 때, carry_happen이 true가 되면 반드시 그 소는 패스합니다. 만약 false라면, 그 소를 태우거나 태우지 않는 경우 두가지 다 해봅니다. 

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int N;
int W[20];
int ans;
 
void InputData(){
    cin >> N;
    for (int i=0 ; i<N ; i++){
        cin >> W[i];
    }
}
 
bool carry_happen(int a, int b){
    // 자릿수 계산
    int a_ = static_cast <int>(log10(a)) + 1;
    int b_ = static_cast <int>(log10(b)) + 1;
    for(int i = 0; i<max(a_,b_); i++){
        if((int)(a/pow(10, i))%10 + (int)(b/pow(10, i))%10 >= 10) {
            return true;
        }
    }
    return false;
 
}
 
void dfs(int index, int sum_, int num_cow){
    if(N-index + num_cow < ans) return;
    if(index >= N){
        ans = max(ans, num_cow);
        return;
    }
    if(carry_happen(sum_, W[index])){
        dfs(index+1, sum_, num_cow);
    }
    else{
        dfs(index+1, sum_, num_cow);
        dfs(index+1, sum_+W[index], num_cow+1);
    }
 
}
 
 
void solution(){
    dfs(0, 0, 0);
 
}
 
 
int main(){
 
    InputData();// 입력받는 부분
    // 여기서부터 작성
    solution();
 
 
    cout << ans << endl;//출력하는 부분
    return 0;
}