백준[1107] - 리모컨

문제

백준 1107 문제 보기

접근 방법

완전 탐색 방법을 활용해 문제를 풀었다. 모든 키의 조합을 활용해 최소한의 버튼 클릭을 구하는 방법이다.

• +, -로 이동하는 경우.
• 숫자 키로만 이동하는 경우.
• 위 두가지를 조합하여 이동하는 경우.

다음과 같은 조합을 적절히 활용해 정답을 구할 수 있다. 일단 +와 -로만 이동이 가능 한 경우는 단순한 계산으로 처리가 가능하다. 입력된 목표 채널 - 100의 절대값은 + 또는 -를 활용해 접근하는 최소값이다.
나머지의 경우는 모든 자리에 0 ~ 9까지의 숫자를 대입해 정답을 구할수 있다.

주의해야할 점은 목표 채널의 자릿수와 완전 탐색으로 접근하는 자릿수가 일치하지 않아도 정답이 나올수 있다는 점이다. 예를 들어 목표 채널이 999이고 리모컨의 숫자가 1과 0만 사용 가능할때 999의 3자리가 아닌 1000의 4자리수로 이동해야 한다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int N, M, size = 0;
int ans = 987654321;
int num[10];
vector<int> remote;

int dfs() {
    // 입력 받은 자릿수보다 하나 작은 경우를 계산
    if(size - 1 > 0 && remote.size() == size - 1) {
        string n = "";
        // 선택된 키 조합을 문자열로 저장
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        // 문자열을 다시 임시 숫자로 저장
        int numTemp = stoi(n);
        // 가야될 채널과 임시 숫자 사이의 차를 저장
        int diff = abs(N - numTemp);
        // 채널과 임시 숫자의 차이 + 입력된 숫자의 길이를 비교
        ans = min(ans, size - 1 + diff);
    }
    // 입력 받은 자릿수와 같은 경우를 계산
    if(remote.size() == size) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int numTemp = stoi(n);
        int diff = abs(N - numTemp);
        ans = min(ans, size + diff);
    }
    // 입력 받은 자릿수보다 하나 큰 경우를 계산
    if(remote.size() == size + 1) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int numTemp = stoi(n);
        int diff = abs(N - numTemp);
        ans = min(ans, size + 1 + diff);
        return 0;
    }

    for(int i = 0; i < 10; i ++) {
        // 숫자가 막혀있지 않다면
        if(num[i] != 1) {
            remote.push_back(i);
            dfs();
            remote.pop_back();
        }
    }

    return 0;
}

int main() {

    scanf("%d", &N);
    scanf("%d", &M);

    memset(num, 0, sizeof(num));

    int t = N;

    // 입력된 채널의 자릿수 확인
    while(1) {
        t /= 10;
        size ++;
        if(t < 1) {
            break;
        }
    }

    for(int i = 0; i < M; i ++) {
        int temp;
        cin >> temp;
        num[temp] = 1;
    }

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

    dfs();

    ans = min(ans, abs(N - 100));
    printf("%d", ans);
    return 0;
}