백준 BOJ 1107번

---

접근 방법

 

처음엔 고장나지 않은 버튼으로만 target과 가장 가까운 번호를 만든 후에 카운트하고 최소값을 선택하려 했다.

이때 target과 가장 가까운 번호를 어떻게 만들어야 하는지 고민했는데, brute force 문제더라.

0부터 999999까지 모든 번호에서 +, - 로 target까지 이동한 후 최소값을 구하면 되는 문제였다.

 

target이 500000이 최대지만, 최대값이 999999인 이유는 9를 제외하고 모든 버튼이 고장났을 경우에 999999에서 시작하는 경우도 포함되어야 하기 때문이다.

 

0부터 999999까지 버튼을 누르는 횟수를 계산해서 최소값을 반환하면 된다. 

 

---

코드

import java.util.*;

public class Main {
   static boolean broken[] = new boolean[10]; //고장난 버튼
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      int M = in.nextInt();
      int answer = Math.abs(N - 100);
      for(int i = 0; i < M; i++){
         broken[in.nextInt()] = true;
      }
      
      for(int i = 0; i < 1000000; i++){
         int len = check(i);
         if(len > 0){
            int count = Math.abs(i - N);
            if(answer > len + count) answer = len + count;
         }
      }
      System.out.println(answer);
      in.close();
   }
   public static int check(int a){
      if(a == 0) {
         if(broken[0]) return 0;
         else return 1;
      }
      int length = 0;
      while(a > 0){
         if(broken[a%10]) return 0;
         length++;
         a /= 10;
      }
      return length;
   }
}