[BruteForce] 백준 1107: 리모컨

예전에 한 번 리뷰했었던 문제인데, 지금 다시 풀어본 풀이가 좀 더 깔끔하다고 생각되어 다시 포스팅한다.

 

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

1107번: 리모컨

 

이동하고자 하는 목표 채널(N)을 입력받고, 고장난 버튼들을 입력받아 이 버튼들을 0~9까지의 vector에서 제외해 사용가능한 버튼들의 vector, "usableBtns"를 만든다.

// fill usableBtns vector
    for (int i = 0; i < 10; i++)
    {
        usableBtns.push_back(i);
    }
    int input;
    for (int i = 0; i < disalbedBtnsNum; i++)
    {
        cin >> input;
        int inputIdx = findTargetIdx(input, usableBtns);
        swap(inputIdx, usableBtns.size() - 1, usableBtns);
        usableBtns.pop_back();
    }

 

우선적으로 버튼 키를 사용하지 않고 오직 +/-  채널 이동만 사용해서 목표 채널로 이동하려면 몇 번 버튼을 눌러야 하는지 구한다.

// move only using +/-
    if (currentChannel != targetChannel)
    {
        minBtnsNum = abs(currentChannel - targetChannel);
    }
    else if (targetChannel == currentChannel)
    {
        minBtnsNum = 0;
        cout << minBtnsNum;
        return 0;
    }

 

그 다음으로는 앞서 구한 사용 가능한 버튼(usableBtns)으로 이동 가능한 번호로 이동한 후, 거기서 다시 +/- 버튼을 사용해서 목표 채널까지 이동하는 경우의 버튼 입력 수를 구한다. 이 때, 시작 채널이 100이고 목표 채널 N이 [0,500,000] 사이에 있다는 조건이 주어졌기 때문에, 나는 0~1,000,000 까지의 경우의 수만 파악하였다. 깡으로 +/- 버튼을 눌러서 이동하는 것이 인접 번호로 이동해서 +/- 버튼을 누르는 것보다 오래 걸릴 것이고, 모든 버튼이 다 고장나 있고 N = 500,000인 경우 최대 499,000 번의 채널 이동이 필요하다. 따라서 999,000 번 이상으로 이동해서 다시 -버튼을 눌러서 이동하는 경우는 불필요한 경우라고 생각하였기 때문에 배제한 것이다.

 

for (int i = 0; i < 1000000; i++)
    {
        if (isNumberReachable(i, usableBtns))
        {
            int newCase = countDigits(i);
            newCase += abs(i - targetChannel);
            minBtnsNum = min(minBtnsNum, newCase);
        }
    }

0~1,000,000까지 모든 경우의 수를 살펴보면서, 만일 그 번호가 usableBtns의 조합으로 만들어질 수 있다면 isNumberReachable이 true를 반환한다. isNumberReachable 함수의 return 값이 true라면, countDigits를 통해서 해당 번호로 이동하는 데 필요한 버튼 입력 수를 구하고, 거기서 다시 +/- 버튼을 통해 목표 채널에 도달하기 위한 추가 버튼 입력 수를 구한 후 이를 minBtnsNum에 update해 주는 방식으로 구현하였다. 

 

전체 코드 첨부하고 마친다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <limits>

using namespace std;

void swap(int i, int j, vector<int> &v)
{
    int tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

int findTargetIdx(int target, vector<int> &v)
{
    int result = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == target)
        {
            result = i;
            break;
        }
    }
    return result;
}

int countDigits(int number)
{
    if (number == 0)
        return 1;
    int cnt = 0;
    while (number != 0)
    {
        cnt++;
        number /= 10;
    }
    return cnt;
}

bool isNumberReachable(int number, vector<int> &v)
{
    bool b = true;
    vector<int> nums;

    if (number == 0)
    {
        nums.push_back(number);
    }
    else
    {
        while (number != 0)
        {
            nums.push_back(number % 10);
            number /= 10;
        }
    }

    if (nums.size() == 0)
    {
        return false;
    }

    for (int i = 0; i < nums.size(); i++)
    {
        bool isDigitFound = false;
        for (int j = 0; j < v.size(); j++)
        {
            if (nums[i] == v[j])
            {
                isDigitFound = true;
                break;
            }
        }
        if (!isDigitFound)
        {
            b = false;
            break;
        }
    }

    return b;
}

int main()
{
    vector<int> numpadBtns;
    vector<int> usableBtns;
    int currentChannel = 100;
    int targetChannel;   // N
    int disalbedBtnsNum; // M
    int minBtnsNum = numeric_limits<int>::max();

    cin >> targetChannel >> disalbedBtnsNum;

    // fill usableBtns vector
    for (int i = 0; i < 10; i++)
    {
        usableBtns.push_back(i);
    }
    int input;
    for (int i = 0; i < disalbedBtnsNum; i++)
    {
        cin >> input;
        int inputIdx = findTargetIdx(input, usableBtns);
        swap(inputIdx, usableBtns.size() - 1, usableBtns);
        usableBtns.pop_back();
    }

    // move only using +/-
    if (currentChannel != targetChannel)
    {
        minBtnsNum = abs(currentChannel - targetChannel);
    }
    else if (targetChannel == currentChannel)
    {
        minBtnsNum = 0;
        cout << minBtnsNum;
        return 0;
    }

    for (int i = 0; i < 1000000; i++)
    {
        if (isNumberReachable(i, usableBtns))
        {
            int newCase = countDigits(i);
            newCase += abs(i - targetChannel);
            minBtnsNum = min(minBtnsNum, newCase);
        }
    }
    cout << minBtnsNum;
}