1107번: 리모컨

Memo

로직 설명

• 고를 수 있는 채널(자릿수)에서 + - 까지 써서(갯수) N에 도달할 수 있는 최소 값을 구합니다.

Code

제출 날짜

2021/05/06

메모리

2016 KB

시간

32 ms

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

int N, M, len, ans;
bool broken[11];

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

void input()
{
	int tmp;

	io_faster();
	std::cin >> N >> M;
	for (int i = 0 ; i < M ; i++)
	{
		std::cin >> tmp;
		broken[tmp] = 1;
	}
	len = std::to_string(N).size();
}

void brute(int channel, int depth)
{
	if (depth && std::abs(channel - N) + depth < ans)
		ans = std::abs(channel - N) + depth;
	if (depth == len + 1)
		return ;
	for (int i = 0 ; i < 10 ; i++)
		if (!broken[i])
			brute(channel * 10 + i, depth + 1);
}

void solve()
{
	ans = std::abs(100 - N);
	brute(0, 0);
}

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

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