[백준 / BOJ] C++ 1107 리모컨

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

1107번: 리모컨

문제

풀이

브루트포스 알고리즘이다.

 

문제에서의 함정이있는데, 이동하고자 하는 채널 N은 0 <= N <= 500000이라고 나온다. 

하지만 리모컨으로 500000의 채널이 이동 가능하다면, 999999의 채널도 이동이 가능하다.

 

처음에 500000까지 반복을하며 시간을 많이 소비한 문제..

전체 완전탐색하면 그렇게 난이도가 높은 문제는 아니다.

 

우선 Seach 함수에서 고장난 버튼으로 바로 이동이 가능한지 나누어가며 탐색한다.

이후 버튼을 눌러서 갈 수 있는 채널이면 누르는 횟수를 cnt에 저장해준다.

 

마지막으로 이동하고자 하는 채널의 수가 '+' 또는 '-'로 이동하는 횟수, 즉 입력된 횟수보다

작을경우에만 값을 갱신시켜준다.

 

아래 코드를 참조하자.

 

Code ( C++ )

#include <iostream>
#include <cmath>

using namespace std;

bool remote[10];
int N, M;

int Search(int n) 
{
    int cnt = 0;
    if (n == 0) 
    {
        if (!remote[0])
            return 1;
        else
            return 0;
    }

    while (n) 
    {
        if (remote[n % 10])
            return 0;
        n /= 10;
        cnt++;
    }
    return cnt;
}

int main() 
{

    cin >> N >> M;

    for (int i = 0; i < M; i++) 
    {
        int btn;
        cin >> btn;
        remote[btn] = true;
    }

    int result = abs(100 - N);
    for (int i = 0; i <= 1000000; i++) 
    {
        int count = Search(i);
        if (count > 0) 
        {
            int b = abs(N - i);
            if (result > b + count)
                result = b + count;
        }
    }

    cout << result;
}