백준 1107번 리모컨 (C++)

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

1107번: 리모컨

 

내 접근

- Greedy 문제라고 생각했다. 만약 4987 인데 9가 금지라면 9대신에 가장 근접한 8을 배치하고 49XX보다 48XX가 더 작으므로 격차를 최소로 하기 위해 사용할 수 있는 가장 큰 값을 배치하여 4888로 지정하고 4987 - 4888 + 자리수 = 103 

이렇게 생각했다. 그러나 이러면 자리수가 바뀔 때를 계산할 수 없다. 예를 들어

9998 이고 9가 금지라면 10000 에서 두번 내리는게 가장 빠르다. 그러나 위 방법으로 하면 반드시 자릿수를 맞추기 때문에 9998 - 8888 로 개산된다. 이것은 오답이다.

 

위와 같은 방법을 생각했기 때문에 난 Greedy 하다고 생각했는데 문제 유형은 브루트포스였다.

 

그리고 결국 0부터 10만까지 그저 비교해보면 되는 문제였다. 

이 것을 눈치채느냐 나처럼 어렵게 가느냐가 문제였던 것 같다. 그러나 나처럼 최적해를 찾는 방법도 가능할 것 같기는 하다. 다른 블로그에도 최적해를 찾는 방식을 사용한 사람들이 있는 것 같지만 이것이 가장 정해이다.

 

시간복잡도는 10만 * 6 = 약 60만으로 여유롭게 가능하다. 그러나 to_string 함수로 조금 더 비용이 들 순 있지만 유의미한 정도는 아니기에 충분히 해결가능했다. 

 

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

bool visited[10] = { false, };

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int tmp;
		cin >> tmp;
		visited[tmp] = true;
	}
	int answer = abs(100 - N);
	for (int i = 0; i <= 1000000; i++) {
		string str = to_string(i);
		//cout << str << endl;
		bool flag = true;

		for (int j = 0; j < str.size(); j++) {
			if (visited[str[j] - '0'] == true) {
				flag = false;
				break;
			}
		}
		if (flag == true) { 		
			int ans_candidate = abs(N - i) + str.size();
			//cout << ans_candidate << endl;
			answer = min(answer, ans_candidate);
		}
	}

	cout << answer << '\n';
}