백준 1107

백준 1107 : 리모컨

1. 100에서 시작해 +,- 로 해당 채널까지 가는 경우
2. 채널 숫자를 입력하고 그 후 +,- 로 해당 채널까지 가는 경우
3. 채널 숫자를 입력할 때, 자릿수별로 어떤 숫자를 입력할까를 고민하면 반례가 굉장히 많이 생기고 복잡하다.
4. 따라서 0~1,000,000 번 숫자까지 중에 반복하면서
5. 만약에 숫자 중에 망가진 버튼이 포함된 숫자가 있으면 건너뛴다.
6. 망가진 숫자가 없다면, (숫자의 길이 + 숫자와 주어진 채널의 차이) 값과 최소값을 비교한다.
7. 최초의 최소값은 (100 - 주어진 채널) 의 절대값이고, 6을 수행하며 최소값을 갱신한다.

시간 복잡도 : 6 10 10^6 = 6*10^7

4번에서 50만이 아니라 100만까지 하는 이유는 채널이 50만일때 0에서 가는 경우와 100만에서 가는 경우를 고려해야 하기 때문이다

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, btn[10];

bool btnBroken(string s) {
	for(int i=0; i<s.size(); i++) {
		int temp = s[i]-'0';
		if(btn[temp]==1) {
			return 1;
		}
	}
	
	return 0;	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	
	cin>>n>>m;
	for(int i=0; i<m; i++) {
		int in;
		cin>>in;
		btn[in]=1;
	}
	
	//1. save diff between n and 100 (use +, - only)
	int ans=abs(n-100);
	if(ans<3) {
		cout<<ans<<'\n';
		exit(0);
	}

	//2. select channel and calculate diff
	for(int i=0; i<=1000000; i++) {
		string s=to_string(i);
		if(btnBroken(s)) { //don't consider if btn is broken 
			continue;
		}
		else {
			int cand = s.size();
			cand+=abs(i-n);
			
			ans = min(ans, cand); 
		}
	}
	
	cout<<ans<<'\n';

	
	return 0;
}