1107 리모컨

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

1107번: 리모컨

리모컨 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

27097

6033

4117

21.878%

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

 

<개인풀이>

생각보다 어려웠다 고려해야 하는 수들이 복잡했고, 반례를 처리하기 힘듬.

 

처음 잘못된 접근

1. +,- 키만 채널을 고르는 방법(1), 숫자를 누른다음 +,-로 고르는 방법(2)로 분류

2. 해당 자리수에 고장난 버튼이 없으면 절대값으로 고장나지 않은 버튼을 찾기 시작.

 ->반례가 있음. 찾고자 하는 채널이  1000, 고장난 버튼 1인경우,

     1의 근사치 2를 찾으면 2xxx번대 에서 가는것보다, 999에서 채널하나올리는게 빠름,

 

다시 접근 (올바른 풀이)

1.  위 1과동일 (+,- 키만 채널을 고르는 방법(1), 숫자를 누른다음 +,-로 고르는 방법(2)로 분류)

2.  위 2의 반례로 0채널 부터 쭉 올라감,

3.  2번을 하면서 고장난 버튼을 제외하고 목표채널에 근사한 모든숫자를 찾는다.

4.  3번에서 찾은 모든 숫자들의 자릿수를 계산,  (자릿수는 숫자 버튼 누르는 횟수)

5.  시작 채널(100)과  3번에서 구한 숫자들중 가장 차가 적은 최소 값을 찾는다

     -> 5번까지하면 고장난 버튼을 제외하고 목표채널에 가장 근사한 채널이 무엇인지 알게됨.

6. 5번을통해 (목표버튼 - 근사채널)의 차이는 숫자버튼(자릿수) 과 +,-버튼의 (수)를 더한값을 찾음

 

6 .번까지하면 목표채널에서 가장 가까운 고장나지 않는 버튼을 찾고, (+,-)키를 통해 몇번

  더 눌러야 하는 지 알게됨 

 

7. 여기까지 답이 아니고, 위 1번과 비교를 해야한다. 왜냐하면

   102에 고장난버튼이 1개가 3번 숫자버튼 이라면,

 100 -> + -> + 키를 통해 2번만에 갈수있지만,

 

6 번을 통해 찾으면 1번숫자 버튼 + 0번숫자버튼 + 2번숫자버튼 3번으로 오답이나버리기 때문

 

따라서.

1번 에서 (+,-)버튼으로 갈수 있는 방법과, 6번을 통해 나온 수를 비교하여 최소값을 출력,

 

그리고 예외처리중에 0번 채널이 들어오는경우이다 i=0 부터 들어갈때

 -> 1번의 100번채널에서 0번가는 방법 (99번) > 1 버튼 ->  (-)버튼 (2번)

 

0번인데 0번이 정상인겨우, 0번 한번누르면 끝, => 자릿수 가 0

 -> 1번의 100번채널에서 0번가는 방법 (99번) > 0 버튼 (1번)

 

#include<stdio.h>
#include<math.h>

bool check[10];
int result;
int result_bfc;

int Isvalue(int ch);

int bfc(int n);
int main(void)
{
	int n = 0, m = 0;
	scanf("%d", &n);
	scanf("%d", &m);
	int temp = 0;

	//false : unbroken , true : broken
	for (unsigned short i = 0; i < m; ++i)
	{
		scanf("%d", &temp);
		check[temp] = true;
	}
	
	int ch = 100-n;
	if (ch<0) ch = -ch; //99, 101, 102 와같이 위아래 버튼으로 눌렀을경우.

	for (unsigned int i = 0; i < 1000000; ++i)
	{
		int length = 0;
		length = bfc(i); //자리수
		
		if (length) //고장난 버튼을 제외한 숫자버튼을 누른경우
		{
			int onbutton = n - i; //n:목표채널, i: 누른숫자
			if (onbutton < 0) onbutton = -onbutton;

			if (ch > onbutton + length) //숫자를 누르고 찾는게 최소면 ch 는 최소값, 
				ch = onbutton + length; //102와 같이 숫자를 누르는거보다 +,-가 빠르면 버튼최소
		}


	}
	printf("%d\n", ch);
	return 0;
}

int bfc(int n)
{
	//exception 
	if (n == 0)
	{
		if (check[0] == false) return 1; //0채널 버튼 정상, length = 자릿수는 1
		                                 //onbutton = 0채널 - 0채널 =0
		else return 0; //0채널 고장난경우,
	}

	//
	int temp = n;
	int length = 0;
	while (temp)
	{
		if (check[temp % 10]) return 0;
		length++;
		temp /= 10;
	}
	return length;
}

추가

리모컨을 저렇게만드는 수빈이 부시고싶음.