[백준 1107] 리모컨(Java)

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

이 문제는 완전탐색으로 풀 수 있습니다. 다음의 프로세스대로 문제를 접근하시면 됩니다.

1. 시작 지점이 100이므로 100에서 N까지 (+,-) 버튼으로만 이동하는 경우의 수를 기본 결과값으로 저장
2. N이 6자리 수이므로 1자리 수에서 6자리 수의 모든 숫자들을 대입
3. 고장난 버튼을 사용하는지 체크
4. 고장난 버튼을 사용하지 않았을 경우 누른 횟수의 최솟값 출력
   4-1. 최소 이동 횟수 = 리모컨으로 버튼을 누르는 횟수 + (+,-) 버튼으로 조정하는 횟수
   = 반복문 내에서 대입한 숫자의 자릿수 + 대입한 숫자와 N과의 차이
   4-2. 이렇게 구한 횟수와 기존 (+,-) 버튼으로만 이동하는 경우의 수와의 최솟값을 출력

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N,M;
    static boolean[] isBroken = new boolean[10];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        if(M!=0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<M;i++){
                int idx = Integer.parseInt(st.nextToken());
                isBroken[idx] = true;
            }
        }

        // 시작 지점이 100이므로 100에서 N까지 (+,-) 버튼으로만 이동하는 경우의 수를 기본 결과값으로 저장
        int res = Math.abs(N - 100);
        // N이 6자리 수이므로 1자리 수에서 6자리 수의 모든 숫자들을 대입
        for(int curr=0;curr<999999;curr++){
            String str = String.valueOf(curr);
            int len = str.length();

            // 고장난 버튼을 사용하는지 체크
            boolean isBrokenButtonUsed = false;
            for(int i=0;i<len;i++){
                int idx = str.charAt(i) - '0';
                // 고장난 버튼을 사용한다면 사용 불가한 수이므로 사용 제외
                if(isBroken[idx]){
                    isBrokenButtonUsed = true;
                    break;
                }
            }

            // 고장난 버튼을 사용하지 않았을 경우 누른 횟수의 최솟값 출력
            if(!isBrokenButtonUsed){
                // 최소 이동 횟수 = 리모컨으로 버튼을 누르는 횟수 + (+,-) 버튼으로 조정하는 횟수
                // len : 리모컨으로 버튼을 누르는 횟수
                // Math.abs(curr - N) : 리모컨으로 누른 채널에서 +,-로 조정하는 횟수
                int min = Math.abs(curr - N) + len;
                // 기존 결과값과 새로 구한 결과값 중 더 작은 값을 출력
                res = Math.min(res,min);
            }
        }
        System.out.println(res);
    }
}