[JAVA] 백준 1107번_리모컨

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

1107번: 리모컨

---

💡유형 : 브루트포스

• 가능한 수들을 조합해 1차적으로 수를 만든 뒤, 거기서 + / - 해서 N에 도달해야 함
  • 가능한 번호로 숫자를 조합하는 과정에서 완전 탐색 진행함
• 주의해야 할 점
  • 가능한 숫자 조합에서 N으로 도달할 때 +/- 버튼 누르는 횟수에 숫자 만드는데 누른 버튼 횟수를 더해야 함
  • 100에서 바로 +- 누르는게 제일 빠를 수 있으므로 cnt = |N - 100|로 세팅해줌
  • 처음에는 버튼 누르는 횟수 세는 조건을 N과 자릿수가 같은 수가 완성 된 경우로 설정했는데, 예외사항 존재함 
    • N = 1000, 고장난 버튼이 0, 1 인 경우 2222에서 가는 것보다 999에서 가는게 빠름
    • 반대로 N=999, 고장난 버튼이 9인 경우 888에서 가는 것보다 1000에서 -1하는게 빠름 
    • => 길이가 1 이상인 경우 검사하되, 길이가 목표 숫자 자리 +1 인 경우 탐색 중지

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int pCnt, len, N, tmp;
    static ArrayList<String> button = new ArrayList<>(Arrays.asList("0", "1", "2", "3", "4", "5"
            , "6", "7", "8", "9"));
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        len = (N + "").length(); //목표 채널 길이
        int M = sc.nextInt();
        while (M-- > 0) {
            button.remove(sc.nextInt()+"");
        }
        pCnt = Math.abs(N - 100);
        searchMin("", 0);
        System.out.println(pCnt);
    }

    private static void searchMin(String s, int length) {
        if(length >= 1) {
            tmp = Math.abs(N - Integer.parseInt(s)) + length;
            pCnt = Math.min(pCnt, tmp);
            if(length - 1 == len) return;
        }
        for (int i = 0; i < button.size(); i++) {
            searchMin(s + button.get(i), length + 1);
        }
    }
}

❗ ArrayList 초기에 값 넣은 상태로 초기화
 : new ArrayList<>(Arrays.asList("0", "1", "2", "3", "4", "5" , "6", "7", "8", "9"));