[BOJ_1107][Brute_Force]리모컨

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - 버튼을 이용해

특정 채널로 이동하려고 할 때 망가지지 않은 버튼을 이용해 이동하려면 최소 몇 번 버튼을 눌러야 하는지 계산하는 문제입니다. 유의해야 할 점은, 목표 채널로 이동하기 위해 숫자를 누르지 않는 것이 빠를 수 있다는 점입니다. 또한, 목표채널 N이 어디에 존재할 지 모르므로 뺄셈 연산 후 절대값을 취해줘야 함을 잊지 말아야 합니다. 

 

1. 모든 번호를 Brute Force 로 탐색(0 에서 500000까지의 N 이 존재하지만, 이동할 수 있는 채널의 제한은 없으므로 1000000 까지의 채널을 탐색하도록 합니다. 망가진 버튼이 무엇인가에 따라 N 범위를 벗어난 채널에서 이동하는 것이 더 빠를 수 있습니다. 

 

2. 고른 채널을 숫자를 눌러 이동할 수 있는지를 확인합니다. 

 

3. 고른 채널에서 몇 번 더 +, - 버튼을 눌러 원하는 채널로 이동할지 확인합니다. 간단한 뺄셈 연산입니다. 

 

---

정답 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std; 

vector<int> br;
bool broken[10];

// check if the chosen number can be used 
// returning len 0 means that only + or - will be used
int possible(int num) {
	int numcpy = num;
	
	if (num == 0) {
		if (broken[0]) return 0;
		else return 1;
	}

	int len = 0;
	while (numcpy > 0) {
		if (broken[numcpy % 10]) return 0;
		len++;
		numcpy /= 10;
	}
	return len;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	
	int m, n;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		broken[tmp] = true;
	} // input 

	// Brute Force through each possible number
	int ans = abs(n - 100);
	for (int i = 0; i <= 1000000; i++) {
		int num = i;
		int len = possible(num);
		if (len > 0) {
			int press = abs(num - n);
			if (len + press < ans) ans = len + press;
		}
	}

	cout << ans << '\n';
	return 0;
}

 

오답

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std; 

vector<int> br;
int m, n;
bool broken[10];

int countpress(int pick) {
	// count the presses for final pick
	int pickcpy = pick;
	int press = 0;

	if (abs(n - pickcpy) < abs(100 - pickcpy)) {
		while (pickcpy) {
			pickcpy /= 10;
			press++;
		}
	}
	press += abs(n - pick);
	return press;
}

bool check(int num) {
	int cpy = num;
	// guessed number 0
	if (num == 0) {
		if (broken[num] == true) return false;
		else return true;
	}
	// not 0 
	while (cpy > 0) {	
		if (broken[cpy % 10] == true) {
			return false;
		}	
		cpy /= 10;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp; 
		broken[tmp] = true;
	}

	// pick c to move to 
	if (n == 100) {
		cout << 0 << '\n';
		return 0;
	}
	int pick = 100;
	int ans  = abs(n - 100);
	int anscpy = ans;

	for (int num = 0; num < 1000000; num++){
		bool possible = true;
		possible = check(num);
		if (possible == false) continue;
		if (abs(num - n) < anscpy) {
			pick = num;
			anscpy = abs(num - n);
		}
	}

	//cout << pick << '\n';

	// counts number of presses
	int res = min(ans, countpress(pick));
	cout << res << '\n';

	return 0;
}