[1107] 리모컨

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

1107 - 리모컨

본문

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

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	256MB

---

풀이

원하는 채널로 가기 위해서는 어떻게 해야할까? 채널을 입력하거나, 만약 가까운 위치에 있다면 +나 - 해줘서 채널을 찾아갈 수 있다. 그때마다 버튼을 눌러야하는데, 버튼 누르는 횟수를 최소화하고 싶다는 것이 문제의 요점이다.

위에서 얘기했듯, 원하는 채널을 가기 위해서는 결국 ‘경로’를 설정해야한다. 여러가지 경로가 존재할 것이다.

• 기본적으로 채널은 현재 100번이다. 여기서 +나 -를 하면 원하는 채널로 갈 수 있다
• 숫자버튼을 눌러 원하는 채널로 이동한다
• 누를 수 있는 버튼을 통해 특정 채널로 이동한다. 그 이후 +나 -를 하면 원하는 채널로 갈 수 있다
  • 최적의 채널이 몇번인지는 계산할 수 없다. 결국 가능한 모든 채널을 해봐야할 것

3번 경로에 의해, 이 문제가 결국 브루트포스 문제임을 알 수 있다. 모든 채널에 대해 시뮬레이션 돌리면 답을 얻을 수 있다. 모든 채널에 대해, ‘숫자를 만들기 위해 누른 숫자버튼 횟수’ + ‘만들어진 채널과 원하는 채널 차이’ 가 정답이 될 것이다. 모든 채널에 대해 계산하는 코드를 구현하면 끝.

• 참고 알고리즘 : 브루트포스

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 20

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_VAL (2 * 500000)
#define DEC 10

bool isBroken[DEC + 1];
int n;

#define abs(x) (((x) < 0) ? (-(x)) : (x))
#define min(a, b) (((a) > (b)) ? (b) : (a))

bool isValidNumber(int x) {
    if (x == 0) {
        return (isBroken[0] == false);
    }

    bool ret = true;
    while (x > 0) {
        ret &= (isBroken[x % 10] == false);
        x /= 10;
    }

    return ret;
}

int getDigit(int x) {
    if (x == 0) {
        return 1;
    }

    int ret = 0;
    while (x > 0) {
        ++ret;
        x /= 10;
    }

    return ret;
}

int main() {
    scanf("%d", &n);
    int t;
    scanf("%d", &t);
    while (t--) {
        int a;
        scanf("%d", &a);
        isBroken[a] = true;
    }

    int ret = abs(n - 100);
    for (int i = 0; i <= MAX_VAL; ++i) {
        if (isValidNumber(i)) {
            ret = min(ret, abs(n - i) + getDigit(i));

            if (i >= n) {
                break;
            }
        }
    }

    printf("%d", ret);
    return 0;
}