Boj 1107) 리모콘

BruteForce

백준 1107

설명

포인트가 여러개 있음.

1. 시작지점(100)에서 +/- 만을 이용해 움직이는 경우를 고려했는가?
2. 숫자버튼으로 임의의 지점으로 가서 +/- 을 이용해 움직이는 경우를 고려했는가?
3. 2 와 3 경우 를 비교해서 짧은걸 출력했는가?
4. +/- 경우에 결과값이 같지 않음을 인지하고 서로 비교해서 짧은걸 출력했는가?
5. 고장난 버튼에 대해서 Sort 를 했는가? ( 이 풀이에는 상관 없음 )

시간 복잡도

O(n)

코드

bool bTrash[10];

int Base(int c)
{
	int r = 0;
	while (c > 0)
	{
		c /= 10;
		r++;
	}
	return max(r, 1);
}

bool Able(int c)
{
	if (c < 0) return false;
	if (c == 0) return !bTrash[0];

	while (c > 0)
	{
		if (bTrash[c % 10]) return false;
		c /= 10;
	}
	return true;
}

int main()
{
	int to, num_trash;

	cin >> to >> num_trash;

	vector<int> trashes(num_trash);
	for (int i = num_trash-1; i >= 0; i--)
	{
		static int tmp;
		cin >> tmp;
		bTrash[tmp] = true;
	}

	int cur = 100;
	int direct = abs(cur - to);
	for (int diff = 0; diff <= direct; diff++)
	{
		// 애가 Base 가 + 버전보다 더 작거나 같으므로 앞에 와야함
		if (Able(to - diff))  
		{
			int ans = diff + Base(to - diff);
			if (ans > direct) break;
			cout << ans;
			return 0;
		}
		if (Able(to + diff))
		{
			int ans = diff + Base(to + diff);
			if (ans > direct) break;
			cout << ans;
			return 0;
		}
	}

	cout << direct;
}