[백준알고리즘] 브루트포스 - 1107번 리모컨 문제

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

1107번: 리모컨

골드문제.쉽지않네

고장난 수(버튼)를 제외한 나머지 수들로 구성할 수 있는 모든 수를 구해보면서

이동하려는 채널과 가장 차가 작은 수를 구해야하나??

만약 사용가능한 숫자 버튼이 다섯개라면

한자리 수부터 다섯자리 수까지 모든 수를 다 만들어봐야하나??

그렇게 이동하려는 채널과 가장 차가 적은 수를 알아내고 + 또는 -버튼으로 나머지를 메꾸어 채널과 수를 일치시킨다고 하자

숫자 버튼을 누르지 않고 + 또는 -버튼만 눌러 이동하는게 더 좋은 상황이라면..??

(101번 채널로 이동하고자 한다던가..)

+버튼만 눌렀을때의 경우도 따로 그럼 생각해야하는걸까나..

이 방식대로 하려고 해도

우선 남아있는 버튼들로 가능한 모든 수들을 다 만들어 보는 알고리즘이 머릿속으로 잘 안그려진다..

그리고..만약 고장난 버튼이 하나도 없어서 버튼이 0부터 9까지 다 있다면

만들 수 있는 수는 엄청나게 많을텐데 분명 시간초과이지 않을까...

문제 접근을 어떻게 해야할지..

예전같았으면 어떻게든 더 고민을 했겠지만 나는 시간이 무한정 있지 않다

그만 고민하고 강의를 좀 보고오겠다..

 

다시 강의를 찬찬히 듣고 강의 코드를 살펴보았다..

코드보고 감탄했다..이렇게 간결하게 짤 수 있다니!!

이해한대로 코드의 핵심적인 부분 설명을 해 보자면

1부터 1000000(백만)까지의 수들을 버튼으로 누를 수 있는지 아닌지를 하나씩 체크한다음(해당되는 고장난 버튼이 없는값)

(이동하려 하는 채널은 최대 500000이기 때문에 넉넉하게 두배인 백만으로 잡음)

누를 수 있는 채널이라 판단되면 이동하려 하는 채널과 그 차를 구해 +,-버튼을 얼마나 더 눌러야하는지 구하고

그 두개를 더한 값(누를수있는 채널값의 길이수 + 그로부터 가려고 하는 채널까지 눌러야 할 +,-버튼횟수)과

기본값(이떄 초기값은 숫자버튼을 누르지 않고 가려는 채널만큼 +,-버튼만을 누른 횟수가 된다)과 비교해

차가 더 작다면 그 값을 갱신한다

이런식으로 백만까지 쭉 가보면 가장 적은수가 되는데 이게 답이 되는 식이다!

 

이해했으니 이제 혼자 코드를 구현해보겠다

 

package baekjoonWeek3;

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

public class RemoteController { //백준 1107번 리모컨 문제
    static boolean[] broken = new boolean[10]; //고장난 버튼을 표시할 배열, 기본값:false , static을 붙여 생성없이 사용

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int channel = Integer.parseInt(br.readLine());  //목적지 채널
        int M = Integer.parseInt(br.readLine());    //고장난 버튼 개수

        if (M > 0) {    //고장난 버튼 개수가 0이 들어오는 경우 대비
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {   //고장난 버튼 정보를 true로 설정
                int m = Integer.parseInt(st.nextToken());
                broken[m] = true;
            }
        }

        int pressPlusOrMinus;   //추가적으로 눌러야 할 플러스/마이너스 버튼
        int pressCountResult = channel - 100;   //초기값은 그냥 플/마 버튼만 눌러서 가는 횟수로 해준다(채널 100에서 시작이므로 100빼줌)
        if (pressCountResult < 0) { //음수면 양수값으로
            pressCountResult = -pressCountResult;
        }

        int length;
        for (int i = 0; i <= 1000000; i++) {
            length = (Integer.toString(i)).length();
            if (isPossible(i)) {    //이동가능한 채널이라면
                pressPlusOrMinus = channel - i; //목적지 채널과의 차를 구한다 (추가적으로 눌러야 할 +or-버튼횟수)
                if (pressPlusOrMinus < 0) { //음수면 반대로 음수를 붙여 양수로 만들어줌
                    pressPlusOrMinus = -pressPlusOrMinus;
                }
                if (pressCountResult > pressPlusOrMinus + length) { //i의 자릿수만큼 누른 횟수 + 추가적으로 누를 +or-버튼횟수의 합과 비교
                    pressCountResult = pressPlusOrMinus + length;
                }
            }
        }
        bw.write(Integer.toString(pressCountResult));
        bw.flush();
        bw.close();
    }

    static boolean isPossible(int i){
        if (i == 0) {   //0은 따로 체크해준다
            return !broken[0];
        }
        while (i > 0) {
            int check = i % 10;
            if (broken[check]) {    //고장난 버튼이 포함된 수여서 이동불가능
                return false;
            }
            i = i / 10;
        }
        return true;
    }

}

 

고장난 버튼이 없는 경우, i에 0이 들어오는 경우, 음수가 될 경우 등을 고려해 주어야 했다

강의를 본 덕에 접근법을 이해하고 와서

제출은 한번에 잘 되었다.다행이다!