백준 1107번 리모컨 <브루트포스>

이 문제는 도저히 모르겠어서 구글링 했다..

다른 사람들의 풀이를 봐도 도저히 모르겠어서 머리 꽁꽁 싸매고 고민하던 중!

드디어 깨달아버렸다.. 너무 감격한 나머지 흔적을 남기고자 한다.

예를 들어 내가 5457번 채널로 가고 싶다고 하자, 현재 나는 100번 채널을 시청 중이다.

1. | 5457 - 100 | 을 통해 순수 + - 만 이용해 원하는 채널로 가기 위한 횟수를 구한다.
2. 그런 다음 0번 채널부터 1,000,000번 채널까지 반복한다. (인덱스는 i로 설정) 문제에서 주어진 건 500,000이지만 위에서 감소하면서 내려오는 경우도 있으니 1,000,000번까지 고려해준다
3. i번 채널로 이동 가능하면, i번 채널로 가는데 필요한 버튼 누르는 횟수를 계산하여 반환해주고 i번 채널로 이동 불가능하면 그냥 0을 반환한다. ※ 유효하지 않은 버튼을 사용하는 경우이기 때문
4. 만약 반환된 값이 0이 아니라면(= + -가 아닌, 숫자를 눌러서 한번에 도달가능하면), 현재 원하는 채널 5457번에서 i번 채널을 빼주고, i번 채널까지 가는 값(=위에서 반환된 값)을 더해준다.
5. 그리고 1번에서 구했던 값과 비교연산하여 더 작은 것을 cnt변수에 담아준다

-> 0번부터 1,000,000번 채널 중 유효한 버튼을 이용해 도달할 수 있는 채널 번호을 누르는 횟수

+

그 채널에서 원하는 채널까지 + - 버튼 누르는 횟수!

-> 5457번 채널로 가기위해서는 for문을 반복하다가, i가 5455가 되었을 때 check함수는 4를 반환해주고 5455에서 5457을 뺀 값은 2이므로 이 두개를 더한 값은 6이 된다. 이 때 이 값이 만약 현재 cnt변수보다 작다면 cnt를 6으로 갱신하고 다른 최소값이 있는지 for문을 더 돌리며 계산한다.

그렇지만 이 경우에서는 i가 5455일 때 cnt값이 최소이므로 답은 6이 될 것 이다.

#include <iostream>
#include <vector>
using namespace std;

int m,num,n,cnt;
vector<bool> button(10);

int check(int n) {
    // 이동하려고 하는 채널이 0인 경우
    if (n == 0){
        if (button[0]){
            return 0;
        }
        else {
            return 1;
        }
    }
    // 이동 하려고 하는 채널이 0이 아닌 경우
    int len = 0;

    while(n > 0){
        // 버튼이 고장난 경우
        if (button[n % 10]) { // 각 자리 수에 대해서 나머지 연산을 통해 한 자리수 씩 뽑아 내어 고장난 버튼이 있는지 판별
            return 0;
        }
        // 고장난 버튼이 없다면
        n = n / 10;
        len += 1;
    }
    // 리모컨을 누른 횟수 반환
    return len;
}

int main() {
    cin >> n >> m;
    while(m--){
        cin >> num;
        button[num]=true;
    }

    if(n==100) {
        cout << 0;
        return 0;
    }

    cnt = abs(n-100); // + - 만 눌렀을 경우 == 최대 횟수

    for (int i=0; i <= 1000000; i++){ // 0번 채널부터 1000000번 채널까지 모두 검사(브루트 포스)
        int channel = i;

        int push = check(channel);

        if (push > 0) {
            // press : 누른 번호에서 이동하려하는 채널까지의 사용해야 하는 연산자(+, -) 횟수 계산
            int press = abs(channel - n);
            // 최초 100번 채널에서, 연산자만 가지고 몇번을 눌러야 도달할 수 있는지에 대한 count 변수와,
            // (리모컨에서 누른 번호에서부터 이동하려하는 채널까지 연산자를 눌러야하는 횟수)
            // + (c에 대해 반환된 리모컨을 누른 횟수)를 비교하여 더 작은 값을 count에 저장
            if (cnt > press + push)
                cnt = press + push;
        }
    }
    cout << cnt;
    return 0;
}