백준 1107. 리모컨 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/1107

"브루트 포스의 존재, 순서"

예전에 분명히 풀었던 문제인데 풀질 못했다. 반성해야겠다. 

해당 문제는 브루트 포스 즉, "다해보기" 문제이다. 재귀적으로 가능한 경우의 수를 모두 검색한다. 

그렇다면, 언제 까지 재귀를 돌릴 것인가? 즉, 기저사례가 언제 일까?

나는 현재 입력으로 들어온 채널의 길이 +1 까지를 기저사례로 정했다.

번호를 눌러서 갈 수 있는 채널들로부터 목적지 채널까지 거리를 비교해줬다.

(처음에는 번호를 누르는 것과 동일하게 +,- 버튼도 함께 돌려 버려서 이상한 결과가 나왔다.. 

51 > (-) > 50 > 0 > 500 이런 식으로...) 

아무튼... 버튼을 누르고, 해당 위치에서 목적지 채널까지 거리를 비교한다... 이것이 +,- 에 대한 처리임.

import java.io.IOException;
import java.util.Scanner;
 
class Main {
 
    static int N,M;
    static boolean[] broken = new boolean[10];
    static int min;
    static int limit;
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        
        for (int i = 0; i < M; i++) {
            broken[sc.nextInt()] = true;
        }
        
        limit = (N+"").length()+1;
        min = Math.abs(N - 100);
        
        for (int i = 0; i < 10; i++) {
            if(broken[i]) continue;
            solve(1,i);
        }
        System.out.println(min);
    }
    
    static void solve(int cnt, int ch) {
        
        if(limit < cnt) {
            return ;
        }
        
        min = Math.min(min, cnt + Math.abs(N - ch));
        
        for (int i = 0; i < 10; i++) {
            if(broken[i]) continue;
            solve(cnt+1, (ch * 10) + i);
        }
    }
    
}