티스토리 뷰
https://www.acmicpc.net/problem/1107
최솟값의 초기값은 초기 채널에서 +,-만 눌러서 목표채널로 이동하는 횟수. 이 값보다 버튼 클릭 횟수가 커지면 최솟값이 될 수 없다.
채널을 0부터 시작해서 1씩 증가시키며 현재 채널이 리모컨으로 입력 가능한지 확인한다.
입력 가능하면 목표채널까지 몇번만에 갈 수 있는지 확인.
이때 리모컨 입력 횟수는 "현재 채널을 입력하고 +,-만 입력하여 목표채널로 간 횟수"
이 값이 최솟값보다 작으면 최솟값을 업데이트 해준다.
현재 채널을 입력하는 횟수는 채널의 자릿수 길이고 +,-만 입력하여 목표채널로 가는 횟수는 현재채널과 목표채널의 차이값이다.
채널 탐색 범위가 500,000을 초과하는 이유
예를 들어 목표채널이 500,000인데 6 버튼 만 입력 가능할 경우 최소 클릭 횟수는 666,666 채널을 입력한 후 -버튼을 166,666번 누르는 것이기 때문에 500,000 보다 높은 채널의 경우도 고려해야한다.
C++ code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <iostream> #include <vector> using namespace std; bool check(vector<bool>& avail, int n){ if(n == 0 && avail[n] == false) return false; while(n){ if(avail[n%10] == false) return false; n /= 10; } return true; } int distance(int a, int b){ return a > b ? a-b : b-a; } int length(int a){ int len = 0; do{ len++; a /= 10; }while(a); return len; } int main(){ int n; cin >> n; int m; cin >> m; vector<bool> avail(10,true); int temp; for(int i = 0; i < m; i++){ cin >> temp; avail[temp] = false; } int min = distance(n,100); for(int i = 0; i < 1000000; i++){ if(check(avail,i)){ temp = distance(n,i) + length(i); min = min < temp ? min : temp; } } cout << min; return 0; } | cs |