골5 1107 리모컨 - 브루트포스

 

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

1107번: 리모컨

 

 

 

	static boolean[] broken = new boolean[10];
	
    public static void bf_1107(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 이동 원하는 채널
        int m = sc.nextInt(); // 고자안 채널 갯수
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            broken[x] = true; // 트루면 고장!
        }

        //1. N까지 + 또는 - 버튼으로만 움직이는 경우
        //단순히 Math.abs로 계산하면 된다.
        int ans = Math.abs(n - 100);

        //2. N과 가까운 번호를 누른 후, + 또는 - 버튼으로 움직이는 경우
        //고장 난 버튼을 제외할 방법을 생각해 주어야 한다.
        //possible_1107 함수에서 모듈러(%)를 사용하여 한자리씩 고장 난 버튼인지 확인하고,
        //고장 난 버튼이 하나라도 포함되어 있다면 누를 수 없는 번호이므로 return 0 해준다.
        //그러고 나서 숫자 버튼 누르는 횟수 + 방향 버튼 누르는 횟수가 더 작은 값인지 확인해 준다.
        for (int i = 0; i <= 999999; i++) {
            //c로 숫자버튼만을 이용해서 이동이 가능한지, 가능하다면 몇 번의 버튼을 누르는지 구하는 변수
            int len = possible_1107(i);
            if (len > 0) {
                //숫자버튼으로 n에 최대한 인접하게 이동한후 +또는 -를 몇 번 눌러야 하는지 구하는 변수
                int press = i - n;
                if (press < 0) press = -press;

                // 최소 이동 횟수 계산
                if (ans > len + press) {
                    ans = len + press;
                }
            }
        }
        System.out.println(ans);
    }
	
    private static int possible_1107(int c) {
        if (c == 0) { //0일때 예외처리
            if (broken[0]) {
                return 0;
            } else {
                return 1;
            }
        }
        int len = 0;
        while (c > 0) {
            // 고장난 버튼이 있는 경우
            if (broken[c % 10]) {
                return 0;
            }
            // 숫자버튼 누르는 횟수 증가
            len += 1;
            c /= 10;
        }
        return len;
    }

 

 

 

 

참고

https://velog.io/@hammii/%EB%B0%B1%EC%A4%80-1107-%EB%A6%AC%EB%AA%A8%EC%BB%A8-java

https://1-7171771.tistory.com/37