[BOJ 1107] 리모컨

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

1107번: 리모컨

 

문제는 현재 위치가 100일 때 주어진 위치로 가기 위해서 리모컨을 최소 몇 번을 클릭해야 하느냐는 문제입니다.

대신 리모컨의 숫자 버튼 일부가 고장 나 있는 상태일 수 있다는 것이죠

 

현재 위치에서 문제에서 주어지는 위치로 갈 수 있는 방법은 일반적으로 생각하면 2가지 경우입니다.

1. + 또는 - 버튼을 사용하여 해당 위치로 간다. 100보다 큰 위치이면 +, 100보다 낮은 위치이면 - 를 이용해서 가는 것이죠

2. 숫자 버튼으로 눌러서 간다.

 

그렇지만 2의 경우는 해당 채널의 숫자 버튼이 고장 났을 수 있습니다. 

그래서 2의 경우를 2가지로 나눌 수 있습니다

2 - 1. 해당 숫자보다 낮은 수 이면서 갈 수 있는 수 중 최댓값으로 이동 후 +를 이용해 이동

2 - 2. 해당 숫자보다 큰 수 이면서 갈 수 있는 수 중 최솟값으로 이동 후 -를 이용해 이동

 

이렇게 해서 처음의 1번 경우와 새로운 2가지의 경우를 합해서 총 3가지의 경우를 모두 알아낸 후 그중 제일 작은 값을 돌려주면 이번 문제를 풀 수 있습니다

 

예제를 통해서 알아보겠습니다

예제 1

1. 100에서 + 또는 - 를 이용해서 움직인다. 5457 - 100 = 5357 

 

2. 5457은 현재 7이 고장 났기 때문에 바로 갈 수 없습니다. 따라서 5457 보다 낮은 수 중 갈 수 있는 수 중 최댓값에서 +로 이동해 보겠습니다. 그러려면 일단 5457 보다 낮은 수이면서 갈 수 있는 수 중 최댓값을 구해보겠습니다. 5456 은 갈 수 없습니다 (6이 불가능). 5455는 갈 수 있습니다. 그러면 5455가 5457 보다 낮은 수 이면서 갈 수 있는 수중 최댓값입니다. 이제 5455에서 마지막 행동인 +로 이동을 하면 5457 - 5455 = 2 입니다. 

최종적으로 클릭 수는 5455로 가기 위한 클릭 4번(자릿수) + 5455에서 5457로 가는 +버튼 2번 = 총 6번입니다

 

3. 이번엔 5457보다 크면서 갈 수 있는 수 중 최솟값을 구해보겠습니다. 5458 불가능 (8이 불가능), 5459 가능합니다. 따라서 5459에서 이동하면 됩니다. 자세한 설명은 2번의 경우와 비슷하므로 생략하겠습니다

따라서 최종 클릭 수는 5459로 가기 위한 클릭 수 4번 + 5457로 가기 위한 - 버튼 2번 = 6번입니다

 

따라서 5457로 가기 위한 최소 클릭 수는 6번이 되는 것입니다.

 

 

예제 2로 한 번만 더 해볼까요? 이번엔 설명은 생략하고 결과 값만 보여드리겠습니다

예제 2

1. 500000 - 100 = 499900

2. 500000 보다 작은 수 중 최댓값 = 155555, 155555 + (500000 - 15555) = 34451

3. 500000 보다 큰 수 중 최솟값 = 511111, 511111 + (511111 - 500000) = 11117

따라서 최소 클릭 수는 11117 입니다

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
#include <math.h>
#include <stack>
#include <map>

using namespace std;

bool arr[10] = { true, true, true, true, true,
		true, true, true, true, true };

bool possibleNumber(int num)
{
	auto result = true;
	while (num >= 0)
	{
		if (arr[num % 10] == false)
		{
			result = false;
			break;
		}
		num /= 10;
		if (num == 0)
			break;
	}

	return result;
}

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

	int N = 0, M = 0;
	cin >> N >> M;

	for (auto i = 0; i < M; i++)
	{
		auto temp = 0;
		cin >> temp;
		arr[temp] = false;
	}

	auto minNum = abs(N - 100);

	for (int i = N; i >= 0; i--)
	{
		if (possibleNumber(i))
		{
			auto val = i;
			auto cnt = abs(N - i);
			while (val >= 0)
			{
				cnt++;
				val /= 10;
				if (val == 0)
					break;
			}
			minNum = min(minNum, cnt);
			break;
		}
	}

	for (int i = N + 1; i <= 999999; i++)
	{
		if (possibleNumber(i))
		{
			auto val = i;
			auto cnt = abs(N - i);
			while (val >= 0)
			{
				cnt++;
				val /= 10;
				if (val == 0)
					break;
			}
			minNum = min(minNum, cnt);
			break;
		}
	}

	cout << minNum;

	return 0;
}