[백준] 1107번 리모컨 C++

 

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

알고리즘 분류

브루트포스 알고리즘

---

Hint

시간이 2초라서 C++로는 생각보다 많은 연산을 할 수 있습니다

1초당 1억 번의 연산을 한다고 보통 가정합니다

 

N의 범위가 50만이므로

각 자리 수를 2^6번(최대 자리 기준)으로 가정한다해도

약 3000만번의 연산밖에 걸리지 않습니다

 

bool array로 사용 가능한 Button을 관리하면 쉽습니다

---

Solution

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main() {
	int N, M;
	bool Button[10];
	for (int i = 0; i < 10; i++) Button[i] = true;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a;
		cin >> a;
		Button[a] = false; // 사용 못하는 버튼 false로
	}

	bool ch[1000001];
	for (int i = 0; i < 1000001; i++) {
		ch[i] = true;
		string a = to_string(i);

		for (int j = 0; j < a.size(); j++) {
			if (!Button[a[j]-'0']) {
				ch[i] = false;
				break;
			}
		}
	}

	int diff = abs(N - 100);

	if (ch[N]) {
		if (to_string(N).size() > diff)
			cout << diff;
		else
			cout << to_string(N).size();
	}
	else {
		if (N == 0) {
			int up = N;
			while (true) {
				up++;
				if (ch[up]) {
					if (to_string(up).size() - N + up < diff)
						cout << to_string(up).size() - N + up;
					else
						cout << diff;
					return 0;
				}
			}
		}
		else {
			int down = N, up = N;
			while (true) {
				down--;
				if (ch[down]) {
					break;
				}
				if (down == 0) {
					down = -999999;
					break;
				}
					
			}
			while (true) {
				up++;
				if (ch[up]) {
					break;
				}
			}

			if (N - down > up - N) {
				if (to_string(up).size() + up - N < diff)
					cout << to_string(up).size() - N + up;
				else
					cout << diff;
			}
			else {
				if (to_string(down).size() + N - down < diff)
					cout << to_string(down).size() + N - down;
				else
					cout << diff;
			}
		}
	}
}