[BOJ-1107] 리모컨(JAVA)

백준 1107 리모컨

 

1107번: 리모컨

 

문제 설명

 

 - 수빈이는 리모컨을 이용하여  TV 채널을 돌리려고 한다.

 

 - 리모컨은 0부터 9까지 숫자와 +, - 버튼이 있다.

 

 - 수빈이가 이동려는 채널은 N이다. 

 

 - 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하라.

 

 - 수빈이가 지금 보고 있는 채널은 100번이다.

 

---

 

입력 값

 

 - 첫째 줄에 수빈이가 이동려고 하는 채널 N이 주어진다.

   ( 0 <= N <= 500,000 )

 

 - 둘째 줄에는 고장난 버튼의 개수 M이 주어진다.

   ( 0 <= M <= 10 )

 

 - 고장난 버튼이 있는 경우에는 셋째 줄에 고장난 버튼이 주어진다.

   ( 같은 버튼이 여러 번 주어지는 경우는 없다. )

 

 

---

 

예제

 

---

 

 

문제 분석

 

 - 수빈이가 이동하려는 채널은 최소 0에서 최대 50만이다.

   그리고, 이동을 위한 버튼은 최소로 눌러야 하기 때문에 숫자를 이용하여 만들 수 있는 값은 100만 미만이다.

 

 - 왜냐하면, 100에서 50만을 만들기 위해서는 +버튼을 49만9900번을 눌러야 한다.

   즉, 이것과 같은 숫자로 50만을 만들기 위해서는 숫자 버튼 998994를 누르고, -를 49만8994번 누르면 된다.

   998994보다 큰 숫자를 누르면, 반드시 100에서 시작하는 숫자보다 커지게 된다.

 

 - 즉, 모든 숫자는 길어야 6자리의 숫자이라는 것이다.

 

 - 각 숫자는 0~9를 가질 수 있기 떄문에, 최대 6자리의 숫자를 만들 수 있는 경우의 수는 $10^6$ = 1,000,000 이다.

 

 - 해당 숫자를 만들고, (해당 숫자-100)을 하면 몇 번으로 +, - 버튼을 눌러야 하는지 알 수 있다.

 

 - 그러므로 해당 숫자를 만들고, 해당 숫자에서 N까지 +, - 버튼을 몇 번 눌러야 하는지 판단하면 된다.

 

 - 결론적으로, 0~9를 이용하여 6자리 숫자를 만들 수 있는 모든 경우를 살펴보고, 

    해당 숫자에서 N을 만들기 위해 +, - 버튼을 몇 번 누르는지 계속해서 최소 값을 찾아 갱신하면 된다.

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int result=Integer.MAX_VALUE;

    public static int N,M;
    public static int NSize;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());

        M = Integer.parseInt(bf.readLine());

        NSize = String.valueOf(N).length();

        boolean numbers[] = new boolean[11];
        if(M>0){
            StringTokenizer st =new StringTokenizer(bf.readLine());
            for(int i=0;i<M;i++){
                numbers[Integer.parseInt(st.nextToken())]=true;
            }
        }

        result = Math.abs(N-100);

        StringBuilder nowNumber = new StringBuilder();

        findNum(numbers,nowNumber);

        System.out.println(result);
    }

    public static void findNum(boolean numbers[],StringBuilder nowNumber){

        if(nowNumber.length() > 6){
            return;
        }
        if(nowNumber.length()>0){
            int nowN = Integer.parseInt(nowNumber.toString());
            int nowSize = String.valueOf(nowN).length();
            result = Integer.min(Math.abs(N-Integer.parseInt(nowNumber.toString()))+nowSize,result);
        }

        for(int i=0;i<=9;i++){
            if(!numbers[i]){
                nowNumber.append(i);
                findNum(numbers,nowNumber);
                nowNumber.setLength(nowNumber.length()-1);
            }
        }
    }
}