[C/C++] 백준 1107번 - 리모컨

 

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 1000000000 //  1억
int N, M, x;
int check[10]; 
int ans,tmp;

int solve(int x)
{
	int tmp = x;
	int len = 0;
	bool flag = true;

	if (x == 0) // 0번만 예외처리
	{
		if (check[0] == 1) //0번 버튼 고장났을 때
			return INF;
		else len = 1;
	}

	while (tmp > 0)
	{
		if (check[tmp % 10] == 1)
		{
			flag = false;
			break;
		}
		else // 고장나지 않았다면,
		{
			tmp /= 10;
		}
		len++;
	}

	if (flag == true)
	{
		return abs(x - N) + len;
	}
	else return INF;
}

int main()
{
	cin >> N;
	cin >> M;
	ans = abs(N-100);

	// 고장난 버튼 체크 (고장났다면 1)
	for (int i = 0; i < M; i++)
	{
		cin >> x;
		check[x] = 1;
	}
	
	for (int i = 0; i <= 888888; i++)
	{
		ans = min(ans, solve(i));
	}
	
	cout << ans;
}

 

풀이 방법

 

check[i] : i번 버튼의 고장 유무(고장 났을 시 1로 표시)

cin >> N;
cin >> M;
ans = abs(N-100);

// 고장난 버튼 체크 (고장났다면 1)
for (int i = 0; i < M; i++)
{
	cin >> x;
	check[x] = 1;
}
	
for (int i = 0; i <= 888888; i++)
{
	ans = min(ans, solve(i));
}

먼저 이 문제의 답인 ans변수에 초기값을 100번채널에서 N번 채널까지 '+'혹은'-'버튼으로만 이동했을 때의 누른 횟수로 설정해줍니다. 그리고 탐색범위 i는 0부터 88만 888까지 설정해주었는데 이동하려는 채널이 50만이고 9번 버튼 빼고 다 고장 났다고 했을 때 100에서 50만까지 이동하는게 99만 999에서 50만까지 이동하는 것보다 짧습니다. 그러나 만약 8번빼고 모든 버튼이 고장 난 경우에는 100에서 50만까지 이동하는것 보다는 88만 888에서 50만까지 이동하는 게 더 짧습니다. 따라서 탐색할 범위의 최대값은 88만 888로 설정하였습니다.(뭐 어차피 100만으로 설정하여도 시간 초과 안되니 상관은 없습니다...ㅎ)

solve함수에는 파라미터로 0번부터 88만888번까지 보내어 해당 채널을 버튼으로만 이동할 수 있는지 의뢰(?)합니다.

 

int solve(int x)
{
	int tmp = x;
	int len = 0;
	bool flag = true;

	if (x == 0) // 0번만 예외처리
	{
		if (check[0] == 1) //0번 버튼 고장났을 때
			return INF;
		else len = 1;
	}

	while (tmp > 0)
	{
		if (check[tmp % 10] == 1)
		{
			flag = false;
			break;
		}
		else // 고장나지 않았다면,
		{
			tmp /= 10;
		}
		len++;
	}

	if (flag == true)
	{
		return abs(x - N) + len;
	}
	else return INF;
}

먼저 x가 0번일 경우에는 0번이 고장났다면 INF를 리턴하고, 고장나지 않았다면 어차피 0은 while문에 진입하지 않으므로 수의 길이 len은 1로 설정합니다.

0이상의 수들에 대해서는 while문에서 한 자리씩 고장 난 버튼이 없는지 확인하고 고장난 버튼이 없다면 x번에서 N번까지의 '+'혹은'-'를 누르는 횟수 + 수의 길이를 리턴하게 됩니다.

 

 

www.acmicpc.net/problem/1107

1107번: 리모컨