[백준] boj 1107 java "리모컨" - (부르트포스, 완전탐색)

리모컨 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

61511

14544

9997

22.457%

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

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

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

---

풀이 접근

이문제가 완전탐색이라니... 완전탐색이라니..!!!

처음 접근할때는, 예외처리를 해준 후, 원하는 채널의 각 자리 수에 가장 근접한 수를 구한후, + - 횟수를 구해주었다.

 

이 방법이 맞는 줄알앗는데.. 전혀 아님 계속 틀림, 예외가 계속나옴 ㅠ

 

2시간후,, 구글링을 해보니 완전 탐색이란다..ㅠㅠ

 

[완전탐색 정답 코드]

package solved.Class;


import java.io.*;
import java.net.Inet4Address;
import java.util.*;



public class Main {
    static int now = 100;

    static boolean remotecon[] = new boolean[10];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int chanel = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        if(n!=0) {
            String temp[] = br.readLine().split(" ");

            for (String str : temp) {
                int broken = Integer.parseInt(str);
                remotecon[broken] = true;
            }
        }

        if(chanel==100)
            System.out.println(0);
        else if(n==10){
            System.out.println(Math.abs(chanel-now));
        }
        else{
            int ans = Math.abs(now-chanel);

            //목표채널 최대 자리수
            for(int i=0;i<1000000;i++){
                //i까지 이동한 후, +,-로이동 브루트포스
                String number[] = Integer.toString(i).split("");

                boolean flag = true;
                //숫자로 이동 가능한지
                for(String index : number){
                    if(remotecon[Integer.parseInt(index)]) {
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    ans = Math.min(ans,number.length+Math.abs(i-chanel));
                }
            }
            System.out.println(ans);
        }

    }
}

---

[처음 접근 틀린 코드]

package solved.Class;


import java.io.*;
import java.util.*;



public class Main {
    static int now = 100;

    static boolean remotecon[] = new boolean[10];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int chanel = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        if(n!=0) {
            String temp[] = br.readLine().split(" ");

            for (String str : temp) {
                int broken = Integer.parseInt(str);
                remotecon[broken] = true;
            }
        }

        if(chanel==100)
            System.out.println(0);
        else if(n==10){
            System.out.println(Math.abs(chanel-now));
        }
        else{
            int nearby = check_nearby_chanel(chanel);
            int size = Integer.toString(nearby).length();
            System.out.println(Math.abs(chanel-nearby)+size);
        }
    }

    public static int check_nearby_chanel(int chanel){
        String chanel_str = Integer.toString(chanel);
        int size = chanel_str.length();
        int number[] = new int[size];

        for(int i=0;i<size;i++){
            int chanel_index_number = Integer.parseInt(chanel_str.substring(i,i+1));

            int before_number = get_before_number(chanel_index_number);
            int after_number = get_afeter_number(chanel_index_number);

            number[i] = Math.abs(before_number-chanel_index_number) < Math.abs(after_number-chanel_index_number) ? before_number: after_number;
        }
        int result=0;
        for(int i=0;i<size;i++)
            result+=number[i]*Math.pow(10,size-1-i);
        return result;
    }

    private static int get_before_number(int chanel_index_number) {
        int result = Integer.MAX_VALUE;
        for(int i=chanel_index_number;i>=0;i--){
            if(!remotecon[i])
                return i;
        }
        return result;
    }
    private static int get_afeter_number(int chanel_index_number) {
        int result = Integer.MAX_VALUE;
        for(int i=chanel_index_number;i<10;i++){
            if(!remotecon[i])
                return i;
        }
        return result;
    }
}