[백준] 1107 - 리모컨 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

1107번: 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1+1된 채널로 이동하고, -를 누르면 -1-1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장 난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

접근방법

  해당 채널 N까지 가는 방법은 여러 가지가 있다. +/-를 통해 끝까지 가거나, 인접 채널 N 까지 간 뒤,  +/-를 통해 가는 방법. 해당 문제는 그러한 접근 중 가장 최소가 되기 위한 버튼 클릭 수를 요구한다. 어떤 방식이 가장 빠를지 고민한 뒤 풀이 방법으로 임해보자.

실패 원인

 처음엔 BFS로 시도했고, 자릿수를 맞춰서도 계산해보았지만, 실패했다.  BFS는 시간 초과가 나왔지만, 어차피 그 외에도 틀릴 요소들이 많았다는 것을 나중에 알았다.(그 외 0번이 고장 나거나, 고장 난 키가 없는 경우를 고려하지 못해 엄청 애먹었다 -_-;;;) 해당 문제에서 제약이 되는 것은 고장 난 키 값이다. 따라서 채널 N에 직접 접근을 못한다면, 그 주변 번호로 접근을 해야한다. 그러나 여기서 자릿수의 최소가 버튼 클릭의 최소를 보증하지 않는다. 예로 고장난 버튼이 9번이고, 채널 N이 4999일 때, 4888보다 5000번이 접근이 훨씬 빠르다. 단순 자릿수 최소가 최소의 답을 보증하지 않는다는 반례이다. 그럼 어떻게 해야 할까?  

 

풀이

  본인은 해당 문제를 브루트 포스로 풀었다. DP로 풀 수도 있을 것 같지만, 너무 많이 틀렸기도 했고,  끝 값이 무한대이기 때문에 혹시라도 구현 미스로 틀릴 것 같은 기분이 들었기 때문이다. 고장 나서 구현이 불가능한 숫자들은 제외하고, 나머지 만들 수 있는 숫자를 만든 뒤, 해당 숫자에서 채널 N까지의 클릭 수를 더 했다. 그런 값들 중 작은 값으로 갱신하여 답을 구현하였다.  

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int target = Integer.parseInt(br.readLine());

        int error_cnt = Integer.parseInt(br.readLine());
        boolean[] arr = new boolean[10];
          if(error_cnt !=0){
            stk = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < error_cnt; i++) {
                arr[Integer.parseInt(stk.nextToken())] = true;
            }
        }

        System.out.println(solution(target, arr));
    }
private int solution(int target, boolean[] arr) {

        // 100부터 순차적으로 갔을때
        int count = Math.abs(target -100);
        for (int i = 0 ; i <= 999999 ; i++){

            int press_cnt =getlen(i,arr);
            if(press_cnt==-1){
                continue;
            }
            int total_cnt=  press_cnt+ Math.abs(target-i);
            count = Math.min(count,total_cnt);
        }


        return count;
    }


    //해당 i에 대해 갈 수 있다면, 자릿수 반환, 없다면 0 반환
    private int getlen(int i,boolean[] arr){
        int result =0;

        //i : 0 인데 고장난경우
        if (i ==0){
            if(arr[0]){
                return -1;
            }
            return 1;
        }

        while(i!= 0){
            if(arr[i%10]){
                return -1;
            }else{
                result++;
                i/=10;
            }
        }


        return result;
    }
}

결과

 

 문제가 생각보다 까다로워서 많이 틀렸다. 생각해보면, 경곗값을 생각하지 못한 것들이다.(입력이 0or Max 일 때의 문제였다.) 그걸 몰라서 고치는데 엄청 오래 걸린 것 같다.(-_-;;) 문제가 틀렸을 때 항상 확인하자!

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.