[BOJ] 1107. 리모컨

모든 경우를 다해보는 브루트포스 문제이다.

브루트포스는 기본적으로 다음4가지로 구현할 수 있다.
1. for문
2. 순열
3. 재귀
4. 비트마스크

이 문제에서는 만들 수 있는 숫자를 모두 해봐야하 알 수 있는 브루트포스 문제여서 숫자를 만들때 재귀를 이용하여 풀었다. 그리고 모든 숫자의 경우에서 answer를 계속 갱신해주는 방식으로 해주었다. 이 문제는 특히 주의할 점이 상당히 많다. 시작점이 100이라는 것과 또한 2번째 입력이 0 일수도 있다는 것 그리고 재귀를 호출할때 0을 제외하므로 맨마지막에 0을 한번 비교해주는 것과 같은 여러가지 주의할점이 있다.

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1107_리모콘_re {
    
    static int target;
    static int targetLen;
    
    static int answer;
    static boolean[] impossible;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        target=Integer.parseInt(br.readLine());
        int n =Integer.parseInt(br.readLine());
        
        if(n==0) {    //모두 가능하다면 100에서 가는것과 문자열길이와 비교하여 답
            answer=Math.min(Math.abs(target-100), countHowLong(target));
            System.out.println(answer);
            return;
        }
        
        st=new StringTokenizer(br.readLine());
        impossible= new boolean[10];
        for(int i=0;i<n;i++) {
            int temp=Integer.parseInt(st.nextToken());
            impossible[temp]=true;    //불가능
        }
        targetLen=countHowLong(target);
        answer=Math.abs(target-100);
        
        for(int i=1;i<=9;i++)
            if(impossible[i]==false)
                dfs(i,1);
        
        if(impossible[0]==false)    //0일때 마지막으로 해주기
            answer=Math.min(answer,countHowLong(0)+Math.abs(target-0));    //마지막0해주기
        System.out.println(answer);
    }
    
    //숫자의 길이를 세어주는 함수
    static int countHowLong(int input) {    
        int len=1;
        while(input/10 !=0) {
            len=len+1;
            input=input/10;
            
        }
        return len;
    }
    
    
    static void dfs(int num,int len) {
        if(len == targetLen+2)    //두자리수 더크면 멈춤
            return;
        
        answer=Math.min(answer, countHowLong(num)+Math.abs(target-num));
        
        for(int i=0;i<10;i++) {
            if(impossible[i]==false) {    //i번째가 사용가능
                dfs(num*10+i, len+1);
            }
        }
        
    }
    
}