[백준/BOJ] 백준 1107번 : 리모컨

www.acmicpc.net/problem/1107

1107번: 리모컨

버튼을 눌러서 이동할 수 있는 모든 채널로 이동하며 그 채널에서 + 또는 -를 통해 목표하는 채널로 가는 것을 통해 그때 버튼 누르는 최소 경우의 값을 구하고 그 값과 시작 채널 100에서 + 또는 - 만으로 목표하는 채널로 가는 경우 버튼 누르는 값과 비교하여 문제를 해결했다. 그런데 버튼을 눌러서 채널을 이동할 때 그 채널이 999900을 넘어 가는 경우는 고려하지 않는다 왜냐하면 이럴 경우 시작 채널에서 + 또는 - 만으로 목표 채널로 가는 게 더 빠르기 때문이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;

int n;
int m;
vector<int> click_check(10, 1);
string can_click = "";
int result = 987654321;

void Solve(string maked)
{
	//채널 999900을 넘어가는 경우는 정답이 될 수 없다
	//왜냐하면 이럴 경우 시작 채널에서 + 또는 - 만으로 목표 채널로 가는게 더 빠르기 때문이다
	if (maked != "" && stoi(maked) > 999900)
		return;

	if (maked != "")
	{
		//현재 채널에서 목표하는 채널로 + 또는 -를 통해 가는 경우 확인
		result = min(result, (int)maked.size() + abs(stoi(maked) - n));
	}

	for (int i = 0; i < can_click.size(); i++)
	{
		if (maked == "0") //0 뒤에는 다른수가 오는것 제외
			continue;

		Solve(maked + can_click[i]);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		click_check[input] = 0;
	}


	for (int i = 0; i <= 9; i++)
	{
		if (click_check[i] == 1)
			can_click += ('0' + i);
	}

	string temp = "";
	Solve(temp);

	//abs(n - 100)는 채널 100번에서 + 또는 - 만으로 목표 채널로 가는 경우
	result = min(result, abs(n - 100));

	cout << result;

	return 0;
}