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

1107번 : 리모컨

---

문제)

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

 

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

 

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

 

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

 

풀이)

 

// 1107. 리모컨
#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
 
using namespace std;
 
int n, m, k;
vector<int> vec;
vector<bool> visited(10, false);
 
int ans = INT_MAX;
 
void recur(int cur, int channel)
{
    // 더 큰 수를 만들고 빼는 경우도 있으므로
    // 여유롭게 +2 자리까지 만들어준다.
    if (cur == k + 2) return;
 
    // 1개 이상 버튼을 눌렀을 경우, 최소값을 구해본다.
    if (cur >= 1) ans = min(ans, abs(channel - n) + cur);
 
    // 고장난 버튼은 넘어간다.
    for (int i = 0; i < 10; i++)
    {
        if (visited[i] == true) continue;
        recur(cur + 1, channel * 10 + i);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    k = to_string(n).length();
    vec.resize(k);
 
    // 고장난 리모컨 버튼 체크
    int temp = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> temp;
        visited[temp] = true;
    }
 
    // 그냥 + - 버튼을 눌러서 이동하는 경우.
    int button = abs(n - 100);
 
    recur(0, 0);
 
    cout << min(button, ans);
 
    return 0;
}
 

---

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

1107번: 리모컨