[BOJ 1107] 리모컨

#문제

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

#풀이

문제 해결 방법에 대해 감이 잘 오지 않았던 문제였습니다.

별에 별 생각을 다했으나.. 쉽게 풀 수 있는 방법이 있어서 충격을...받았습니다..

가장 쉽게 접근 할 수 있는 방법은 모든 경우의 수를 해보는 경우입니다.

즉, 0부터 할 수 있는 모든 채널을 확인하면서 원하는 채널에 가장 적은 버튼 누름으로 가는 방법을 찾아가면 됩니다.

말로만 보면 굉장히 어려울 수 있으나 직접 코드를 보면 이해가기 편하실 겁니다.

채널을 이동할 때 매우 여러가지 경우의 수가 있겠지만, 문제에서 원하는 것은 최소의 버튼 누름이란것을 캐치하셔야합니다!

즉,  + - + - + + + + 처럼 중간에 다른 버튼이 끼여있다면 의미가 없어지며, 

+ - + 3503 처럼 +,- 버튼을 사용하고 숫자 버튼을 사용하여도 앞에 사용한 +,-은 의미가 없어지게 됩니다.

 

따라서, 원하는 채널로 가는 모든 경우의 수는 총 3개입니다.

1. + 혹은 -만 사용하여 채널로 이동
2. 버튼을 사용하여 채널로 이동
3. 버튼이 고장, 근처 채널로 이동 후 + 혹은 -만으로 채널 이동

기본 채널이 100으로 되어있기 때문에 1번의 경우의 수는 단순하게 |N-100|으로 구할 수 있습니다.

이후 모든 채널을 확인 하여야합니다.

이때, 중요한점은 "채널은 무한대 만큼 있다." 입니다.

예를 들어보자면, 만약 원하는 채널이 450000이라고 합시다.

고장난 버튼이 1,2,3,4,5라면?

채널 100번에서 +버튼만 사용하여 해당채널로 도달 할 수 있지만, 600000번 채널에서 -로 가는것이 더 빠를 것입니다.

눈치 채셨습니까??
모든 채널을 확인 할 때, 50만이 넘어갈 수 도 있다는 점입니다.

저도 이것 때문에 무릎을 탁 쳤습니다..

그렇기 때문에 모든 채널을 확인 할 때, 0-50만까지 +버튼으로 50만번, 

그에 반대인 -버튼으로만 50만번을 할 수있는 100만까지 잡아주도록 합시다.

3번 경우의 수도 누를 수 있는 버튼에서 N을 빼주면 간단하게 구할 수 있는 문제입니다.

이제 코드를 보면서 이해하도록 해봅시다~ :)

#코드

#include <iostream>
 
using namespace std;
 
int broken[9];  // 고장 : 1,  고장x : 0
 
//해당 채널로 숫자 버튼을 눌러 갈 수 있는지 확인하는 함수
//갈 수 있다면 버튼을 누를 횟수를 리턴
int checkingMoveChannel(int channel){
    //0번의 경우 밑에 while문에 들어가지 않기때문에 따로 조건을 걸어준다.
    if(channel == 0){
        if(broken[0] == 1)
            return 0;
        else
            return 1;
    }
    int numOfPressBtn = 0;
    //해당 채널을 자릿수 별로 확인
    while(channel > 0){
        //중간에 한개의 버튼이라도 고장났다면 탈락!
        if(broken[channel%10] == 1){
            return 0;
        }
        numOfPressBtn += 1;
        channel /= 10;
    }
    return numOfPressBtn;
}
 
int main(){
    int N,M;
    cin >> N >> M;
    //고장난 버튼 확인
    for(int i = 0; i < M; i++){
        int num;
        cin >> num;
        broken[num] = 1;
    }
    
    //경우의 수 1번(+혹은 -로만 채널에 가는 경우)
    int ans = N - 100;
    if(ans < 0){
        ans = -ans;
    }
    //채널이 무한대 있기때문에 500000번까지만 구하면 오류가 날 수있다.
    for(int i = 0; i <= 1000000; i++){
        //여기서 i는 채널(0~100만)
        int numOfPressBtn = checkingMoveChannel(i);
        //해당 채널은 버튼을 눌러 갈 수 있다.
        if(numOfPressBtn > 0){
            //해당 채널에서 원하는 채널에 가는 경우의 수
            //3번 경우의 수(근처 채널에 가서 +,-만으로만 채널에 도달)
            int pressPMBtn = i - N;
            if(pressPMBtn < 0)
                pressPMBtn = -pressPMBtn;
            //어떤 경우의수가 큰지 확인.
            //numOfPressBtn + pressPMBtn = 숫자버튼을 누른 수 + (+,-)버튼을 누른 수
            if(ans > numOfPressBtn + pressPMBtn){
                ans = numOfPressBtn + pressPMBtn;
            }
        }
    }
    cout << ans << endl;
    return 0;
}