[백준 BOJ][C++]1107번 리모컨 풀이: 브루트 포스

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

1107번: 리모컨

 

 이 문제는 브루트 포스 알고리즘을 사용하여 해결하는 문제입니다. 

 

 우선, 현재 100번 채널에서 N 번 채널까지 이동하기 위해 버튼을 눌러야 하는 최대 횟수는 + 혹은 - 버튼만을 눌러야 하는 경우 입니다. 따라서 100-N의 절댓값이 최댓값이 됩니다. 

 

 브루트 포스 알고리즘을 사용하므로 0번부터 1씩 증가하며 차례대로 모든 경우를 탐색해야겠죠?

 

[풀이 과정]

1. 숫자 num이 고장난 버튼을 포함하고 있지 않은지 확인

2. 포함하지 않는다면 num에서 N번까지 이동 횟수

               = abs(N-num) (+ 또는 - 버튼 누른 횟수) + 숫자 num의 길이 (숫자 버튼 누른 횟수)

3. 0 부터 1000000까지 1~2과정 반복, 이동 횟수가 최소인 값이 정답

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>

using namespace std;

int n;
int m;
bool dis[10] = { false, };

bool is_possible(int num) {
	string s = to_string(num);

	for (int i = 0; i < s.size(); i++) {
		if (dis[s[i] - 48])
			return false;
	}
	return true;
}

int main(void) {

	int ans = 0;

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int d;
		cin >> d;
		dis[d] = true;
	}

	if (n == 100) {
		cout << 0;
		return 0;
	}

	ans = abs(n - 100);

	for (int i = 0; i <= 1000000; i++) {
		if (is_possible(i)) {
			int temp = abs(n - i) + to_string(i).size();
			ans = min(ans, temp);
		}
	}

	cout << ans;

	return 0;
}