[알고리즘/브루트포스/JAVA] 백준 1107 - 리모컨

[알고리즘/브루트포스/JAVA] 백준 1107 - 리모컨

문제: 백준 1107 - 리모컨

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

1107번: 리모컨

사용언어 : JAVA

 

시간제한 : 2초

메모리 제한 : 256 MB

 

 

문제 설명

초기 채널 번호 : 100

 

입력

맞추려는 채널 번호 : N (0 ≤ N ≤ 500,000)

망가진 숫자 번호 개수 :  M (0 ≤ M ≤ 10)

입력 셋 째 줄 : 고장난 버튼들 M개(띄어쓰기로 구분)

 

+, - 버튼 사용 가능

 

문제 해답 : N 채널을 맞추기 위해 눌러야하는 버튼의 최소 수.

 

사용된 알고리즘

사용된 알고리즘 : 브루트포스 알고리즘 (완전 탐색)

 

오답

문제를 풀며 고려하지 못한 테케들이다. 이 테케들을 통과하도록 코드를 고치니 정답 코드로 인정되었다.

0
2
0 1
답:3

10 
9 
1 2 3 4 5 6 7 8 9
답:11

https://www.acmicpc.net/board/view/31853

글 읽기 - ****리모컨 질문게시판에있는 모든 반례 모음****

 

문제 해답

import java.util.Scanner;

public class Main {

    static boolean[] numbers = new boolean[10];
    static int min = Integer.MAX_VALUE;
    static int digit;
    
    static boolean permutation(int n, int count, int num) {
        //만들 수 있는 경우 바로 종료
        if (count > 0 && num == n) {
            min = Math.min(min, digit);
            System.out.println(min);
            System.exit(0);
        }
        if (count == digit+1) {
            min = Math.min(min, Math.abs(num - n) + count);
            return true;
        }
        if (count == digit) {
            min = Math.min(min, Math.abs(num - n) + count);
        }
        for (int i = 0; i < 10; i++) {
            if (numbers[i]) continue;
            if (count > 0 && num == 0 && i == 0) continue;
            boolean result = permutation(n, count+1, num * 10 + i);
            if (result) return false;
        }
        if (count > 0)
            min = Math.min(min, Math.abs(num - n) + count);
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        digit = str.length();
        int n = Integer.parseInt(str);
        int m = sc.nextInt();
        
        for (int i = 0; i < m; i++) {
            numbers[sc.nextInt()] = true;
        }
        min = Math.abs(n - 100);
        permutation(n, 0, 0);
        System.out.println(min);
    }

}

 

느낀 점

바쁘다는 핑계로 최근 알고리즘을 풀지 않았는데 기초적인 완전 탐색에서도 헤메는 것이 충격적이였다. 알고를 다시 열심히 풀어야 할 것 같다.