백준 1107 리모컨

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

 

 

서론

재귀를 이용하여 이동하려고 하는 채널에 가까운 채널의 한 자리씩 부서진 버튼인지 확인하여 풀이하려 했으나 반례가 계속나왔고, 결국엔 해결하기 까다로운 반례를 만나서 브루트포스로 풀이

 

아이디어

0부터 100000(임의의 큰 수)까지 탐색하는데 현재 숫자가 부서진 버튼이 없으면 배열에 저장

부서진 버튼이 없는 숫자들로 저장된 배열 중 목표채널과 가장 가까운 숫자를 변수에 저장

* 이해를 위해 배열로 설명했으나 실제 구현은 코드의 효율을 위해 직전에 저장된 채널과 바로 비교하여 목표채널과 가까운것을 변수에 저장

변수에 저장된 목표채널과 가장 가까운 숫자의 자릿수(숫자버튼을 누른 횟수)와 목표채널로 이동시킨 횟수(+-버튼을 누른 횟수)를 더한값을 결과로 가져옴

그런데 시작채널이 100이라 99는 -버튼 한번만 누르면 되지만 위의 결과는 1 0 0으로 숫자버튼 3개를 누름, 이것의 해결을 위해 100에서 목표채널까지 +-버튼만으로 이동시킨 횟수와 위의 결과값을 비교하여 적은것을 출력

 

구현

// c++

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

#define INF 1000000

int n, m;
int broken[11];
int channelResult = INF;
int channelCnt;
int updownCnt;

bool tfChecker(int input) {
	int digit = 0;
	do  {
		digit = input % 10;
		input /= 10;
		for (int i = 0; i < m; i++) {
			if (digit == broken[i]) return false;
		}
	} while (input > 0);
	return true;
}

int intLength(int input) {
	int output = 0;
	do {
		input /= 10;
		output++;
	} while (input > 0);
	return output;
}

void channelButton() {
	int compareDiff = 0;
	int resultDiff = INF;
	for (int i = 0; i < INF; i++) {
		compareDiff = abs(i - n);
		if (resultDiff > compareDiff) { 
			if (tfChecker(i) == true) {
				resultDiff = compareDiff;
				channelResult = i;
			}
		}
	}
	//cout << channelResult << endl;
	channelCnt = intLength(channelResult);
	//cout << channelCnt << endl;
}

void updownButton() {
	if (n < channelResult) {
		for (int i = n; i < channelResult; i++) {
			updownCnt++;
		}
	}
	else {
		for (int i = n; i > channelResult; i--) {
			updownCnt++;
		}
	}
}

int compare100() {
	int cnt = 0;
	if (n < 100) {
		for (int i = n; i < 100; i++) {
			cnt++;
		}
	}
	else {
		for (int i = n; i > 100; i--) {
			cnt++;
		}
	}
	return cnt;
}
	
int main() {
	cin >> n;
	cin >> m;
	for (int i = 0; i < m; i++) cin >> broken[i];
	channelButton();
	updownButton();

	//cout<< "compare100 : " << compare100() << endl;
	//cout << "channelResult : " << channelResult << endl;
	//cout << "channelCnt : " << channelCnt << endl;
	//cout << "updownCnt : " << updownCnt << endl;

	int result = min(updownCnt + channelCnt, compare100());
	cout << result;

}