[백준 C++] 1107 리모컨 - 브루트포스

1107번: 리모컨

#include <iostream>
#include <string>
using namespace std;

int N, M, C;
bool Broken[10];

bool IsPossible(string CurrentChannel, int Size)
{
	for (int i = 0; i < Size; ++i)
	{
		int Number = CurrentChannel[i] - '0';
		if (Broken[Number])
		{
			return false;
		}
	}

	return true;
}

int CountPush(int Target)
{
	int Push = 1000000;

	for (int Current = 0; Current <= 1000000; ++Current)
	{
		string CurrentChannel = to_string(Current);
		int Size = CurrentChannel.size();
		if (!IsPossible(CurrentChannel, Size))
		{
			continue;
		}

		Push = min(Push, abs(Target - Current) + Size);
	}

	return Push;
}

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

	cin >> N >> M;

	for (int i = 0; i < M; ++i)
	{
		int Button;
		cin >> Button;
		Broken[Button] = true;
	}

	cout << min(abs(N - 100), CountPush(N));
}

---

브루트포스 알고리즘 유형의 문제입니다.

다음 두 가지 상황 중에 더 작은 값을 선택하도록 해서 풀었습니다.

 

1. 현재 채널(100)에서 목표 채널(N)까지 +,- 버튼만 사용했을 때의 횟수: abs(N - 100)

2. 숫자 버튼 입력 후 +, - 버튼 사용을 통해 목표 채널까지 이동했을 때의 횟수

 

2번 단계에서는 숫자 버튼으로 입력한 채널로 0부터 1000000까지 모두 탐색해줍니다.

그리고 각 채널 마다 숫자 버튼으로 입력 가능한지 확인한 후,

입력 가능하다면 +,-로 이동하는 횟수{abs(목표채널 - 해당 채널)} + 숫자 버튼 입력 횟수{해당 채널의 길이}를 구해주고

그 중 가장 작은 값을 출력하도록 해줍니다.