[BOJ] 리모컨

[1107] 리모컨

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

• TV 채널을 리모컨을 이용해 바꾸는 문제
• 버튼 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -
• 일부 숫자 버튼이 고장났다.
• 현재 보고 있는 채널 : 100
• 이동하려고 하는 채널 : N
• 이 때, 리모컨 버튼을 누르는 횟수를 최소로 하는 문제

 

 

Solution - Fail

• 처음에 생각 했던 방법은 내가 이동 가능한 버튼의 집합을 S라고 했을 때,
• 예를 들어 N이 5457이라면 S 집합의 숫자를 사용해 가능한 모든 네 자리 숫자를 만든다. // M
• 최악의 경우는 100에서 시작해서 +나 -로만 이동했을 때의 횟수로 초기화 한다. // answer = Math.abs(N-100)
• 그러면 모든 경우에 대해 answer = Math.min(answer, N - M)을 계산한 최솟값이 정답이 될 수 있다고 생각했다.
• 하지만 N이 10이면서 고장난 버튼이 0과 1일 때의 코너케이스를 만족하지 못하여 실패한 솔루션이 되었다.. T.T(정답은 2(9 -> +), 결과는 14)

 

Solution - Success

• 앞선 코너케이스까지 만족하는 솔루션이 되기 위해서는 정답의 자릿수를 미리 정해서는 안된다.
• 모든 채널의 범위에서 이동하려는 채널 N까지의 최소 이동 횟수를 구해야 한다. 
• 문제에서 채널의 범위는 0 ~ 무한대로 제시 되어있지만, N의 범위가 0<=N<=500,000 이기 때문에, 채널의 범위는 0 <= C <=1,000,000 으로 가정한다.
• C의 범위에서 S집합의 버튼으로 이동 가능한 경우에 한해서 C-N의 최솟값이 정답이 될 수 있다.

 

 

소스코드

import java.util.*;
public class Main {
	static boolean[] broken = new boolean[10];
    static int possible(int c){
    if(c == 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;
    }
    public static void main(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;
        }
        int ans = Math.abs(N-100);
        for(int i = 0; i<=1000000; i++){
        int c = i;
        int len = possible(c);
        if(len > 0){
        	int press = Math.abs(c-n);
            if(ans > len + press){
               ans = len + press;
             }
         }
    }
    System.out.println(ans);
  	}
}