[백준 1107번] 리모컨 - JAVA

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

1107번: 리모컨

풀이

사용한 알고리즘 : DFS, BFS, 중복순열을 사용한 완전탐색

 

풀이전략

 

예외처리해야할 내용들이 많아 평균적인 골드5 문제보다 고생한 문제였다.

 

기본적인 풀이전략은 0~9까지의 원소들 중 제외된 원소를 뺀 나머지 원소들로 중복순열을 생성하고

목표로 하는 값을 생성한 값으로 뺀 뒤, 생성한 값의 자리수를 더하는 것이다.

 

예로 입력의 결과로 {0,2,4,6,7,8,9}를 제외시켜 {1,3,5}라는 원소 집합이 남았을 경우

중복 순열을 사용하여 2개의 원소를 갖는 부분집합을 만든다면

11, 13, 15, 31, 33, 35, 51, 53, 55라는 경우가 있다.

 

그런데 우리가 목표로 하는 값 N이 42라고할 때,

우리가 중복순열로 생성한 값들 중 가장 인접한 수는 35다.

 

이때

(버튼 입력 횟수) = (목표로 하는 값인 N)-(중복순열로 만들어낸 수들중 가장 인접한 수)+(인접한 수의 자리수)

즉, result = 42 - 35 +2 = 9 다.

 

하지만 처음 채널은 100이라고 했으므로

'(목표로하는 수인 N) - 100' 이 위에서 구한 값보다 작으면 결과는  '(목표로하는 수인 N) - 100' 이다.

 

단, 이 문제에서 중복순열을 사용하여 완전탐색을 진행하되 주의할 점은

목표로 하는 수인 N이 1234인 경우 자리수는 4이지만

비교해야할 대상은 자리수가 3, 4, 5인 경우이다.

 

예시로 아래와 같은 입력이 주어졌을 경우

1555
8
0 1 3 4 5 6 7 9 

 

결과 순열로 사용할 수 있는 원소 집합은 {2,8}로

가장 가까운 수로 자리수가 같은 2222를 생각하기 쉽다.

하지만 주어진 집합에서 N과 가장 인접한 수는 888이다.

 

즉, 가지고 있는 원소 집합으로 만들 수 있는 수들 중 가장 인접한 수는

자리수가 같은 경우, 자리수가 1더 작거나 큰 경우로 확장하여 생각해야한다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static ArrayList<Integer> arr = new ArrayList<Integer>();
    static int result[];
    static int minVal=Integer.MAX_VALUE;
    static int lastDepth=0;
    static int answer=Integer.MAX_VALUE;
    static void dfs(int depth){

        if(arr.isEmpty())
        {
            answer=Math.abs(N-100);
            return;
        }

        // 조건들 중 depth!=0을 넣은 이유는 N이 10보다 작아 자리수가 1(lastDepth=1)이면서 
        // 원소 0이 제외됐을 경우, 중복순열을 생성할 때 0이 들어가지 않도록 하기 위함이다.
        if((depth!=0 && depth==lastDepth-1) || depth==lastDepth || depth==lastDepth+1){
            int val=0;
            for(int i=0;i<depth;++i){
                val*=10;
                val+=result[i];
            }

            if(minVal>=Math.abs(N-val)){

                minVal=Math.abs(N-val);

                int inputNumberOfDigits=0;
                if(val==0) inputNumberOfDigits=1;
                else inputNumberOfDigits=(int)Math.log10(val)+1;

                answer = Math.min(answer,minVal+inputNumberOfDigits);
                if(Math.abs(N-100)<answer){
                    answer=Math.abs(N-100);
                }
            }

            if(depth==lastDepth+1) return;
        }

        for(int x:arr){
            result[depth]=x;
            dfs(depth+1);
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        int numberOfDigits=N;
        if(numberOfDigits==0) ++lastDepth;
        while(numberOfDigits!=0){
            numberOfDigits/=10;
            ++lastDepth;
        }

        for(int i=0;i<10;++i){
            arr.add(i);
        }

        result = new int[lastDepth+1];
        int removeArrIndex[] = new int[M];
        if(M!=0) {
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<M;++i){
                removeArrIndex[i]=Integer.parseInt(st.nextToken());
            }
            Arrays.sort(removeArrIndex);

            for(int i=0;i<M;++i){
                arr.remove(removeArrIndex[i]-i);
            }
        }

        dfs(0);
        bw.write(answer+"\n");
        bw.flush();
        bw.close();
    }
}