[BOJ][C++] 백준 1107번: 리모컨

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

1107번: 리모컨

 

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

풀이

완전탐색: 단순히 모든 채널을 보면서 버튼으로 누를 수있는지 보고 해당 조건을 만족하는 경우에 한해 차이의 최솟값을 구했다

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    // 입력
    int n, m, error;
    cin >> n >> m;
    vector<bool> button(10, true);
    for(int i=0; i<m; i++) {
        cin >> error;
        button[error] = false;
    }

    // 연산
    int temp, digit, ans=500000; bool able;
    for(int i=0; i<=1000000; i++) {  // 부루트포스 완전탐색
        temp = i;
        able = true; // 망가지지 않은 버튼으로 i를 누를 수 있는가?
        digit = 0; // i의 자릿수

        while(temp>0){
            digit++;
            if(!button[temp%10]) {
                able = false;
                break;
            }
            temp /= 10;
        }
        if(i==100) {
            able = true;
            digit = 0;
        } else if(i==0) {
            able = button[0];
            digit++; // 0의 자리수가 1인거 표현
        }

        if(able) {
            ans = min(abs(i-n)+digit, ans);
        }
    }
    
    // 출력
    cout << ans;
    
    return 0;
}

/*
 */

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

vector<bool> button;

int digit(int channel) {
    if(channel==100)
        return 0;

    if(channel==0) {
        if(!button[0])
            return -1;
        return 1;
    }
    
    int cnt = 0;
    while(channel>0){
        cnt++;
        if(!button[channel%10])
            return -1;
        channel /= 10;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    // 입력
    int n, m, error;
    cin >> n >> m;
    button.assign(m, true);
    for(int i=0; i<m; i++) {
        cin >> error;
        button[error] = false;
    }

    // 연산
    int diff = abs(n-100);
    for(int i=n; i<=n+100; i++) {
        if(digit(i) != -1)
            diff = min(digit(i)+i-n, diff);
    }
    for(int i=n; i>=0; i--) {
        if(digit(i) != -1)
            diff = min(digit(i)+n-i, diff);
    }
    
    // 출력
    cout << diff;
    
    return 0;
}

/*
 */