BOJ 1107번 리모컨

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

github : https://github.com/junho0956/Algorithm/blob/master/1107/1107/%EC%86%8C%EC%8A%A4.cpp

 

알아야하는 것은 리모컨 채널에 접근할 수 있는 방법이다.

1. + - 버튼만 눌러서 이동한다

2. 누를수있는 버튼으로 이동 후에, + - 으로 이동한다.

 

처음에는 어떻게 가고자하는 버튼에 최대한 가깝게 갈 수 있을까

여러가지 많이 시도해봤는데 4번 연속 틀리면서 좀 더 간단한 방법을 생각해보고자 했다.

어차피 채널은 최대 50만번이여서 완전탐색의 마구잡이식으로 다 확인해볼까 싶어서

필요한 범위내를 전부 탐색해줬더니 의외로 빠른 시간내에 문제를 해결할 수 있었다.

 

.. 알고리즘은 정말 너무어렵다 ..

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
 
int moveCH, broken;
bool brokenBtn[10];
 
bool possible(int ch) {
    int number;
    // 채널이 0번일수도 있다
    if (ch == 0) {
        if (brokenBtn[0]) return true;
        else return false;
    }
 
    while (ch) {
        number = ch % 10;
        ch /= 10;
        if (brokenBtn[number] == false) return false;
    }
 
    return true;
}
 
int click(int ch) {
    if (ch == 0) return 1+moveCH;
    else {
        int num = 0;
        int channel = ch;
        while (ch) num++, ch /= 10;
 
        num += abs(moveCH - channel);
 
        return num;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int i = 0; i < 10; i++) brokenBtn[i] = 1;
    cin >> moveCH >> broken;
 
    for (int i = 0; i < broken; i++) {
        int a; cin >> a;
        brokenBtn[a] = 0;
    }
 
    /*
    채널을 이동할 수 있는 방법
    1. + - 버튼만 눌러서 이동
    2. 임의의 버튼으로 이동한 후에 + - 버튼을 눌러서 이동
    */
 
    // 채널은 최대 50만번까지 있으니 채널의 자리수를 고려하여 100만까지 탐색해본다
    // 기본 값은 + - 버튼으로만 이동하는 경우
    int min_click = abs(moveCH-100);
    for (int i = 0; i <= 1000000; i++) {
        // 채널로 이동이 된다면 이동 후, + - 까지 같이 계산한다
        if (possible(i)) {
            min_click = min(min_click, click(i));
        }
    }
 
    cout << min_click;
}