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

• 접근 방법

처음 접근했던 방법은, 브루트포스로 풀기 보다는 리모콘으로 최대한 그 채널과 근접하게 이동 후에 채널의 차이를 구하는 방식으로 생각했습니다. 또한 이동하려는 채널보다 큰 값과 작은 값 두 부분으로 나누어서 계산하려고 했습니다. 예를 들어, 이동하려는 채널의 번호가 2333 이라고 하면 2,3의 버튼이 고장 났다고 가정할때 3000가 큰 값, 1999가 작은 값이라 생각하고 코드를 작성했습니다. 하지만 이 방법의 문제점은 999 와 같은 값을 원하는 채널로 받았을때 예외케이스가 많이 발생한다는 것이었습니다. 가령 8과 9의 채널이 고장났다면 999보다 큰 값인 1000 을 찾아내야 하는데 그 값을 계산하기 위해서는 결국 브루트포스로 찾아낼 수 밖에 없다는 생각이 들었습니다.

브루트포스 방식으로 계산할 경우 N의 최대값은 500,000이므로 (10의 6승 * 계산하는 각 숫자의 자릿수의 합)이 시간복잡도로 나왔습니다. 따라서 다른 기법을 사용하지 않고 브루트포스를 이용하여 정답을 찾아낼 수 있었습니다.

#include <iostream>
#include <vector>
#include <cstdlib>

int N, M;
std::vector<int> b_channel;
int c_min, c_size;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int tmp;

	input_faster();
	std::cin >> N >> M;
	b_channel.resize(10, 1);
	for (int i = 0 ; i < M; i++)
	{
		std::cin >> tmp;
		b_channel[tmp] = 0;
	}
}

int is_possible(int n)
{
	c_size++;
	if (n <= 9)
	{
		if (b_channel[n])
			return (1);
		else
			return (0);
	}
	if (is_possible(n / 10))
	{
		if (b_channel[n % 10])
			return (1);
	}
	return (0);
}

void print_val()
{
	std::cout << c_min;
}

void solve()
{
	c_min = std::abs(N - 100);
	for (int i = 0 ; i <= 1000000 ; i++)
	{
		c_size = 0;
		if (is_possible(i))
			if (std::abs(N - i) + c_size < c_min)
				c_min = std::abs(N - i) + c_size;
	}
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}