[BOJ/C++] 1107 리모컨

문제

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

풀이

⚠️ 채널은 500,000까지 있지만 이동하려는 채널보다 높은 위치에서 감소하는 범위도 고려해야 하므로 범위를 1,000,000으로

골드 문제라서 알고리즘 엄청 어려운 줄 알았는데 난이도가 높은 문제는 알고리즘을 떠올리기가 어려운 문제였다.

코드

#include <iostream>
#include <cmath>
using namespace std;

int btn[10];

int check(int n) {
	if(n == 0) {
		if(btn[0])	return 0;
		else	return 1;
	}
	
	int cnt = 0;
	while(n > 0) {
		if(btn[n % 10])	return 0;
		n = n / 10;
		cnt += 1;
	}
	
	return cnt;
}

int main() {
	int N, num;
	
	cin >> N >> num;
	for(int i=0; i<num; i++) {
		int tmp;
		
		cin >> tmp;
		btn[tmp] = 1; //고장난 버튼 
	}
	
	int min = abs(N-100); //처음 100번에서 (+,-) 이용해서 몇번 눌러야되는지
	 
	for(int i=0; i<1000001; i++) {
		int cnt = check(i); //리모컨 번호 누른 횟수
		if(cnt > 0) {
			int up_down_cnt = abs(i-N);
			if(min > cnt + up_down_cnt) {
				min = cnt + up_down_cnt;	
			}
		} 
	}
	
	cout << min;
	
	return 0;
}