첫 번째로 푼 풀이 + 두 번째로 다시 풀어볼 때의 풀이가 추가되었다.

[백준]1107번 리모콘

(2:25... ㅋㅋㅋㅋㅋㅋ)

• 버튼 종류 : 0~9의 숫자, +(현재+1) , -(현재-1) 존재
• 채널0에서 '-'를 누름 —> 채널 변화 ❌
• 채널은 무한대 만큼 있으니 '+'에 대한 제한은 없는 상태.
• 목표 채널 : N번
• 주어지는 것 : 고장난 버튼
• 현재 채널 : 100

채널 N으로 이동하기 위해, [ 버튼을 최소 몇 번 ] 눌러야 하는지 구하는 프로그램 작성하기

• 고장난 버튼의 개수도 주어지네 (0개이상 10개 이하)

풀이 생각

• 이문제에서 채널의 이동은
  • 1️⃣ 숫자버튼을 통해 → 특정 숫자로 바로 이동 : 숫자가 n 자리수면 n개의 버튼을 누르는게 된다.-> 그리고 그 특정숫자로부터 n 까지 +나 -버튼을 통해 이동한다. 이 모든 횟수를 더해야한다.
  • 2️⃣ '+ '버튼 , '-'버튼 만을 통해 → "1"단위로의 이동
  • 따라서 1번, 2번 경우중 더 적은 수를 택하는 것

누를 수 있는 숫자 버튼이 5 만 있다하고, target이 500이면
- 555로 이동후 -를 55번 하는게.
- +를 400번 하는 것 보다 덜 든다.

target이 101이면
- 숫자로 101을 누르면 -> 3개의 버튼을 누르는 것 
- + 버튼을 한 번 누르기 -> 1개읩 버튼을 누르는 것 

target이 98이면 
- 숫자로 98 누르면 -> 2개의 버튼
- - 버튼 두 번 -> 2 개의 버튼 누르기  

이외의 경우가 있나?? 

선택의 경우

• 주어진 숫자버튼으로 target과 최대한 가까운 숫자 만들기 → ??? 아무래도 모든 경우의 숫자들에 대해 해 보아야 할 것 같다.

• 완전탐색? → 완전탐색으로 풀어도 괜찮은 편이다.

  • 생각하고 있는 완전탐색 :

    1. 100이 n이 되는데, +1 이나 -1 만을 통해서 달성하는데, 버튼을 몇 번 눌러야 하는지 →simpleCnt로 저장한다. (+와 - 모두 고장나있는 경우라면 Integer.MAX_VALUE를 저장)
    2. n의 자리수가 c라고 한다면
       • c-1자리의 최소 숫자부터 c+1자리의 max 숫자에 대하여, 현재 버튼으로 누를 수 있는 수인지를 확인한다.
         • 누를 수 있는 수라면, ( 해당 수를 위해 누르는 버튼의 수 ) + (해당 수 부터 n까지 +1이나 -1 연산의 개수 ) → numbcnt라고 한다.
         • 만들어지는 모든 수에 대하여 numbcnt와 simpleCnt를 비교하여 더 작은 값을 저장한다.

  • 이러한 완전탐색이 가능한가? YES

    현재 n의 제한 : 50만: 500000 -> 6자리수. 
    100만을 넘는 경우는 조사할 필요가 없다. 
    따라서 만약 n이 6자리수라면 -> 10000 부터 999999 까지만 조사하면 되기 때문에 
    완전탐색을 해도 100만을 넘지를 않는다. 

  • 왜 n-1자리도, n+1자리도 봐야하는가?

    target이 
    1.  999 인 경우 (n+1자리도 봐야하는 이유)
    
    주어진 수가 1과 0만 있다면 
    1000을 만드는게 
    111을 만드는 것보다 더 좋을 거임. 
    
    따라서, target의 자리수 m 이라고 하면 
    m-1자리수 ~ m+1자리수를 모두 만들어 봐야 하나
    - 만들어 볼 것인가 
    아니면 
    - m-1자리수 가장 작은 숫자 ~ max 숫자 해서, 각 자릿수에 고장난 번호가 있으면 그 번호를 버리기를 할 것인가 
    ----> 최대..5자리수 10000~ 99999
    -----> 6자리수 : 100000~ 999999 
    --최대 50만이니, 100만 넘는 거는 안 봐도됨 
    
    2. target이 10000 인 경우인데 버튼 0이 고장나있는 경우 
    9999 에서 +1을 하는게 더 낫기 때문임. 
    

• 이 문제에서는, 자리수를 직접 구하는 함수를 작성하는게 중요한 것 같다.

  • 만약 생각을 덜 하고 싶어서 매 int를 String으로 변환하여 각 자리수가 무엇인지 확인하게 되면 매 번 String을 생성하게 되기 때문에 주의해 줄 필요가 있다.

package cote;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
 * 1 10
 * 1+ 1 = 2 -> 4 -> 8
 * 1 2 4 8 -> 9, 10
 *
 *
 * */
public class Main{
    /*
     * Integer형태로 10000 부터 99999 까지 검사하기를 하면
     * 해당 int에 대한 연산을 수행 해야 한다. 그게 낫겠다
     * */
    public static int resMin = Integer.MAX_VALUE;
    public static int n,m;
    public static boolean[] numbers = new boolean[10];// 0~ 9 까지의 버튼
    public static boolean[] op = new boolean[2]; // +1, -1
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        Arrays.fill(numbers,true);
        Arrays.fill(op,true);
        // 가능한 버튼정보를 어떻게 넣을까? -> char 형태로?
        // +와 -가 있어서..
        // 아니면 그냥 boolean table을 생성하여, 고장났는지 여부를 표시? -> 이 방법을 택함
        if(m>0){
            String nots = br.readLine();
            String[] disabled = nots.split(" ");
            for(String s : disabled) {
                // 고장난 버튼은 -일 수도 +일 수도 있다.고 생각했다.
                try {
                    int numb = Integer.parseInt(s);
                    numbers[numb]=false;
                }catch(NumberFormatException e){
                    if(s.equals("+")){
                        op[0]=false;
                    }else{
                        op[1]=false;

                    }
                }
            }
        }

    }
    public static void solve(){
        int simplecnt =Integer.MAX_VALUE;
        int numbcnt =Integer.MAX_VALUE;
        int tempCnt= Integer.MAX_VALUE;
        // 단순히 +나 - 연산으로 구할 수 있는 경우.
        if(n==100) {
            resMin =0;
            return;
        }
        else if(n>100&&op[0]){        // n 이 100보다 크고, + 연산자가 고장나지 않은 경우
            simplecnt = n-100;
        }else if(n<100 && op[1]) simplecnt=100-n; // n이 100보다 작고, -연산자가 고장나지 않은 경우
        tempCnt = simplecnt;
        // n은 0이상 50만 이하일 수 있다.
        String temp = Integer.toString(n);
        // target의 자리수를 구한다.
        int len = temp.length();
        // target의 후보인 수들의 '자리수'를 초기화한다.
        int len_min =len,len_max = len;
        int min=0,max=0;
        // 500000
        if(len == 6){
            // len-1 자리 부터 len 자리까지
            len_min = len -2;
            len_max = len;
        }else{
            // len-1 자리부터 len + 1 자리까지
            len_min = len-2;
            len_max = len+1;
        }
        // 만약 len 이 한 자리 수 -> min은 0부터 해야함
        if(len_min<=0) min =0;
        else{
            min = (int)Math.pow(10,len_min);
        }
        // len_max = 5 면 99999 해야하니
        // len_max = 6 이면 999999 으로 해야 하니
        max = (int)Math.pow(10,len_max)-1;
        // min부터 max까지의 정수들에 대해 완전탐색한다.
        for(int i=min;i<=max;i++){
            // i라는 숫자가 '숫자버튼을 눌러' 만들 수 있는 것인지 확인한다.
            if((numbcnt=splitNumber(i))==Integer.MAX_VALUE) continue;
            // i가 만들 수 있는 숫자인 경우 -> i에서 n 까지 몇 번의 + or - 연산을 해야하는지 구한다.
            if(n==i) numbcnt+=0;
            else if(n>i&&op[1]){
                numbcnt+= (n-i);
            }else if(n<i && op[0]) numbcnt+=(i-n);
            // 구해진 numbcnt와 tempCnt를 비교한다. tempCnt는 simpleCnt(+로만 or -로만했을 때의 count개수)로 초기화되어있다.
            tempCnt=Math.min(tempCnt,numbcnt);
        }
        // 버튼으로 숫자를 만들 수는 없는 경우, simpleCnt가 최소가 될테니 for문 밖에서도 Resmin을 업데이트 해줘야한다.
        tempCnt=Math.min(tempCnt,numbcnt);
        resMin=Math.min(resMin,tempCnt);
    }
    //최대 6번의 연산을 한다
    // a_n의 정수의 각 자리수를 확인하여, 각 자리에 있는 숫자가 고장난 버튼인지확인한다.
    public static int splitNumber(int a_n){
        int res = Integer.MAX_VALUE;
        int len = (int)Math.log10(a_n) +1;
        if(a_n==0) len = 1;
        // 구성요소중 고장 난 버튼이 있는지 체크한다.
        int next =a_n;
        int cur=0;
        int mul=(int)Math.pow(10,len-1);
        while(mul>9){
            cur = next/mul;
            if(numbers[cur]==false)return res;
            next-= (cur*mul);
            mul/=10;
        }
        cur = next%10;
        if(numbers[cur]==false)return res;

        return len;

    }
    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(resMin);

    }
}

문제의 조건은 +,-가 고장나는 경우는 포함되지 않는 것이었다.

그랬다..

다른 사람 풀이를 보고 느낀 점

• 다른 사람들 풀이를 보니, 전체 수가 100만이기 때문에 , 나처럼 min, max를 하지 않아도 충분히 풀리는 문제였다.

2021-09-20 다시 풀어볼 때

(0:40)

0~9 버튼 중 고장나는 버튼이 주어진다. → 해당 버튼은 누를 수 없다.

0 번에서 - 버튼을 누르면 채널은 변하지 않는다.

N번으로 이동하려 한다.

N번으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는가???

• 현재 채널은 100번이다.

• N은 0이상 50만 이하이다.

• 고장 난 버튼의 개수는 0 이상 10 이하 → 모든 숫자 버튼이 고장 날 수도 있다.

  • +,-로만 이동하게 될 것.

• 두 가지 경우를 생각 해 볼 수 있다.

  • 숫자 버튼을 눌러서 X 번으로 이동한 후 +,-를 통하여 N번으로 가기
  • +,- 버튼만을 이용하여 N번으로 이동하기
  • 두 가지 경우 중 최소의 값을 선택하는 것이다.

• 주어진 숫자 버튼 중, N번에 가까운 숫자를 만들어야 한다.

  • 이를 위해 브루트 포스를 할 것인가?
  • 이것을 이런식으로 생각 해 볼 수 있다. [ 현재 숫자를 조합해서 특정한 숫자를 만든다 ] 라는 것 보다도 [ 특정 숫자를, 현재 숫자들을 조합해서 만들 수 있는가? ] 라는 접근법으로 접근할 수 있다.
  • 따라서 , 문제에서 주어진 N은 0이상 50만 이하이기 때문에, 50만 가지를 완전탐색하는 것이 가능하다.

• 특정 숫자를, 현재 수자들을 조합해서 만들 수 있는가 ?

  • 이를 위하여, 특정 숫자의 각 자리를 확인하는 과정이 필요하다.

50만이 아닌 100만이다

• 또 이 경우를 간과했다.
• N은 50만 까지가 가능하지만, 어떤 숫자의 고장으로 인해 50만보다 높은 숫자에서 "-"를 통하여 이동하는게 더 적은 수가 드는 경우가 있다.
• 그렇다면 50만 보다 큰 수 중 어느 정도의 숫자까지가 가능한가? 를 본다면, 100부터 +와 - 만으로 이동할 경우 50만까지 이동하는 경우가 있으니, 이 수보다는 작은 경우까지만 검증을 해야할것이다. 따라서 넉넉잡아 100만까지로 하는 것이다.

런타임에러(NullPointer)

• m이 0인 경우에도 br.readLine()으로 다음 라인을 받으려고 해서 생긴 문제였다.

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static int n;
    public static int m;
    public static int min = Integer.MAX_VALUE; // 5000000 으로 해두 되겠다.
    public static boolean[] broken = new boolean[10]; //고장난 버튼 -> false
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int temp=0;
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        Arrays.fill(broken,true); //모두 true로 초기화
        if(m>0) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                temp = Integer.parseInt(st.nextToken());
                broken[temp] = false;
            }
        }

    }

    public static void solve(){
        if(n==100) {
            min = 0;
            return;
        }

        // +, -만을 이용하여 이동하는 경우를 생각하기.
        // 현재는 100번에 위치하고 있다. N번과의 차이를 절댓값으로 구한다.
        min = Math.abs((100-n));

        int cnt=0;
        //완전탐색을 한다.
        for(int t=0;t<=1000000;t++){
            // t라는 채널로 이동가능한 경우 -> (100->t ) + ( t-> N ) 의 수를 계산하여 min 과 비교한다.
            if((cnt=isPossible(t))<0)continue;
            // 100 -> t 로 가는데 버튼은 cnt 번 누른다.
            // t- > N 으로 가는데에는 이제 +,- 만을 이용한다.
            cnt += Math.abs((t-n));
            min = Math.min(min,cnt);
        }
    }
    // t라는 숫자를 현재 생성 가능한지 살펴본다 + 생성가능한 경우, t의 자리수를 리턴한다.
    public static int isPossible(int t){
        // 각 자리수를 구한다.
        int cur =t;
        int num = 0;
        int cnt =1;
        // 1의 자리 수 부터 확인한다.
        while(true){
            num = cur % 10 ;
            if(broken[num]==false) return -1;
            cur /=10;
            if(cur ==0) break;
            cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(min);

    }
}