백준 1107 리모컨

브루트 포스 문제이다. 몇 버튼이 고장난 리모콘을 가지고 특정 숫자를 만들건데, 그것이 최소가 되는 경우를 구해라! 이다.

우리가 어떤 채널에 접근할 때는 크게 두 가지 방법이 있다. 현재 채널에서부터 노가다로 하나씩 올리거나 내리는 방법, 그 채널 숫자를 직접 눌러 접근하는 방법. 근데 숫자 버튼 몇개가 고장나면 해당 채널 숫자를 직접 누를 수 없을 가능성이 생긴다. 이 때는, 현재 쓸 수 있는 버튼으로 접근 가능한 가장 가까운 채널로 이동한 뒤 가고싶은 채널로 한 채널씩 이동한다.

 

이 두가지 방법으로 이동 횟수를 구한 뒤, 낮은 횟수를 구하면 된다.

노가다로 이동하는 방법은 그냥 abs(가고싶은 채널 - 100) 을 하면 된다.

가고싶은 채널에 인접하면서 현재 리모콘으로 갈 수 있는 채널은 가고싶은 채널에서부터 i를 늘려가며 위아래로 탐색을 했다.

인접하면서 리모콘으로 갈 수 있는 채널을 구한 뒤, 그 채널의 자리수 + 가고싶은 채널과의 차이를 구해 노가다 방식과 비교했다.

그러면 짠. 답이 나온다.

---

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <climits>

std::vector<int> broken;

int check_available(int ch)
{
    for (int btn : broken)
    {
        int tmp = ch;
        ret = 0;
        if (!ch && btn == 0)
            return false;
        while (tmp)
        {
            if (tmp % 10 == btn)
                return false;
            tmp /= 10;
        }
    }
    return true;
}

int main()
{
    int target, broken_n;
    std::cin >> target >> broken_n;
    for (int i = 0; i < broken_n ; i++)
    {
        int tmp;
        std::cin >> tmp;
        broken.push_back(tmp);
    }
    if (broken.size() == 10)
    {
        std::cout <<std::abs(target - 100);
        return 0;
    }
    int i = 0;
    int cur_chan = 100;
    bool found = 0;
    while(42)
    {
        if (target - i >= 0 && check_available(target - i))
        {
            cur_chan = target - i;
            break;
        }
        if (target + i <= INT_MAX && check_available(target + i))
        {
            cur_chan = target + i;
            break;
        }
        // if (target - i < 0 && target + i > 500000)
        //     break;
        i++;
    }
    int ret = std::min(std::to_string(cur_chan).size() + i, (unsigned long)std::abs(target - 100));
    std::cout << ret;
    return 0;
}

 

브루트 포스 문제들은 구현 문제랑 결이 비슷한 것 같다. 다만 구현 문제의 경우 진짜 문제가 설명하는 그 자체를 만들어야 하지만, 브루트 포스 문제는 조금 생각할 여지가 있는 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.