백준 1107 리모컨 (C++)

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

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

int n, m;
int ans = INF;

bool broke[10];


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n >> m;



    for (int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        broke[temp] = true;
    }

    //100에서 +-를 누르는 경우
    ans = min(ans, abs(100 - n));

    //버튼을 조작하여 가는 경우
    for (int i = 0; i <= 1000000; i++) {

        string temp = to_string(i);
        bool notBroke = true;
        for (int j = 0; j < temp.size(); j++) {
            if (broke[temp[j] - '0']) {
                notBroke = false;
                break;
            }
        }

        if (notBroke) {
            ans = min(ans, (int) (abs(n - i) + to_string(i).length()));
        }

    }

    cout << ans;

    return 0;
}

1. 문제

현재 100번 채널을 시청하고 있다. 이를 리모컨을 사용하여 n번 채널로 바꾸려 하는 데, 리모컨에는 채널을 1 올리는 +, 1 내리는 - 버튼, 0~9까지의 버튼이 있고, 숫자 버튼 중 m개의 고장난 버튼이 주어진다. 이 때 해당 채널로 이동할 때 누르는 버튼의 최소 횟수를 구하라.

2. 풀이

+, -로 이동하는 경우, 숫자를 누르는 경우가 있으므로 브루트포스로 해결할 수 있다. 채널을 이동하는 방법은 다음과 같다.

• 현재 채널(100번)에서 +, -를 눌러 이동하는 경우
• 버튼을 누르고, 한번에 가지 못하는 경우 +, -로 조작하는 경우

두 가지 경우를 구현하여 풀 수 있다.

    bool broke[10];

    for (int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        broke[temp] = true;
    }

우선 고장난 버튼을 확인하여 bool의 형태로 저장한다.

    //100에서 +-를 누르는 경우
    ans = min(ans, abs(100 - n));

현재 채널에서 +, -를 눌러 이동하는 경우 n이 크면 +만, 작으면 -만 눌러 가는 경우가 최소 횟수이다.

    //버튼을 조작하여 가는 경우
    for (int i = 0; i <= 1000000; i++) {

        string temp = to_string(i);
        bool notBroke = true;
        for (int j = 0; j < temp.size(); j++) {
            if (broke[temp[j] - '0']) {
                notBroke = false;
                break;
            }
        }

        if (notBroke) {
            ans = min(ans, (int) (abs(n - i) + to_string(i).length()));
        }

    }

다음은 버튼을 조작하여 가는 경우이다. 모든 채널에 대해 버튼으로 채널을 변경할 수 있는 지 확인한다. 변경할 수 있다면, 해당 채널로 가서(to_string(i).length) +, -을 조작하여 n번 채널로 가는 경우(abs(n-i))를 갱신한다. 채널은 50만까지 주어지므로 100만까지 탐색한다.

모든 채널에 대해 탐색이 끝난 후 ans를 출력하면 정답을 구할 수 있다.