백준 #1107 리모컨

일부숫자버튼이 고장나서 숫자를 원하는대로 못 누르는 리모컨이 있습니다.  이 리모컨에서 최소한의 버튼을 눌러서 원하는 채널을 틀려면 어떻게 할까요?

 

broken remote controller

 

조금은 어려울 수 있는 문제입니다.  고장난 숫자키만 아니라면 BFS로 풀 필요도 없이 숫자로 채널을 바로 선택하거나, 그것보다 적은 횟수의 채널 위아래 버튼을 누름으로써 해결볼 수 있겠죠.  난이도는 Gold V 입니다.  정답벼율이 21.7%로 상당히 낮습니다.

 

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

1107번: 리모컨

 100번 채널에서 입력받을 채널로 변경을 하려고 합니다.  할 수 있는 방법은 고장난 키보드로 가장 근접한 숫자를 고른 후에 채널 위아래를 이용해서 옮기는 방향이 될겁니다.  그런데 몇가지 예외를 챙겨야 합니다.  이것때문에 정답률이 꽤 낮습니다.

 

예외 경우를 대충 처리하고, 변경하고자 하는 채널값을 기준으로 \(\pm s\) 하여 해당 채널을 돌릴 수 있는지 검사합니다.  아무리 숫자가 커도 시작 수가 100이므로 100 이내에는 존재합니다.

 

제가 작성한 프로그램의 결과값입니다.

0 8
0 1 2 3 4 5 6 7

Result:
9

4799 10
0 1 2 3 4 5 6 7 8 9

Result:
4699

43 10
0 1 2 3 4 5 6 7 8 9

Result:
57

43 9
0 1 3 4 5 6 7 8 9

Result:
23

 

제가 짠 소스입니다.  소스는 참고용으로 봐주세요.  (지금 다시 보니까 엉망인 곳이 한두군데가 아니네요.)

//--------------------------------------------------------------------
//  baekjoon #1107 - Remote Controller
//    - by Aubrey Choi
//    - created at 2019-07-03
//--------------------------------------------------------------------
#include <stdio.h>

int ABS(int n) { return n > 0 ? n : -n; }
int DIGIT(int n) { int d; if(n==0) return 1; for(d=0;n;d++,n/=10); return d; }
int main()
{
  int n, c = 100, m, s;
  char broken[10] = {0, };
  scanf("%d", &n);
  scanf("%d", &m);
  for(int i = 0; i < m; i++)
  {
    scanf("%d", &s);
    broken[s] = 1;
  }
  int min = ABS(n - c);
  if(m == 10)
  {
    printf("%d\n", min);
    return 0;
  }
  if(m == 9 && broken[0] == 0)
  {
    if(n+1 < min) min = n+1;
    printf("%d\n", min);
    return 0;
  }
  if(n == 0)
  {
    for(int i = 0; i < 10; i++)
    {
      if(broken[i] == 0)
      {
        printf("%d\n", i + 1);
        return 0;
      }
    }
  }
  if(broken[0] == 0 && n + 1 < min) min = n + 1;
  for(s = 0; ; s++)
  {
    c = n - s;
    if(c > 0)
    {
      while(c && broken[c % 10] == 0) c /= 10;
      if(c == 0) { s += DIGIT(n-s); break; }
    }
    c = n + s;
    while(c && broken[c % 10] == 0) c /= 10;
    if(c == 0) { s += DIGIT(n+s); break; }
  }
  if(s < min) min = s;
  printf("%d\n", min);
}