[BOJ] 1107 : 리모컨 고치기

문제 : www.acmicpc.net/problem/1107

---

백트레킹 브루트포스

[ 알고리즘풀이 ]

 우리는 최대 N이 500,000 이므로 고장나지 않은 버튼들로 0 ~999,999 까지만 만들어보면 된다.

 고장나지 않은 버튼들로 한 번 숫자를 다 만들고 나서부터는 +, - 버튼 말고 누르는 의미가 없으므로,

 0 ~ 999,999 까지 고장나지 않은 버튼들로 만들 수 있는 숫자를 다 만들어 최소 버튼 누르는 횟수를 저장하고 N까지 이동하는데 눌러야되는 +, - 버튼의 횟수를 계산해 최소값을 찾으면 된다.

 

[ 코드구현 C++ ]

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
 
using namespace std;
 
int N, visited[1000001] = {}, K;
bool isBroken[10] = {};
queue<int> q;
 
void makeChannel(string s) {
    for (int i = 0; i < 10; i++) {
        if (!isBroken[i]) {
            s += ('0' + i);
            if (stoi(s) <= 1000000) {
                //cout << "만들어진 채널 : " << s << endl;
                visited[stoi(s)] = s.length();
                makeChannel(s);
            }
            s.pop_back();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    memset(visited, -1, sizeof(visited));
    cin >> N >> K;
    for (int i = 0, x; i < K; i++) {
        cin >> x;
        isBroken[x] = 1;
    }
    // 만들 수 있는 모든 수 들을 만들어본다.
    if (!isBroken[0]) visited[0] = 1;
    for (int i = 1; i < 10; i++) {
        if (!isBroken[i]) {
            string t = "";
            t.push_back('0' + i);
            visited[i] = 1;
            makeChannel(t);
        }
    }
    visited[100] = 0;
 
    int ans = 999999999;
    for (int i = 0; i <= 1000000; i++) {
        if (visited[i] != -1) {
            ans = min(ans, abs(N - i) + visited[i]);
        }
    }
    cout << ans << '\n';
    return 0;
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1107.cpp

travelbeeee/ProblemSolving

---