[백준] 1107번 리모컨

1107 리모컨

문제

---

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

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

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

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

입력

---

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

출력

---

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

---

풀이)

고생했던 문제였다.

처음에는 숫자 n의 각 자리수를 int형 배열에 저장한 뒤

각 자리수에서 고장나지 않은 가장 가까운 수를 찾아서 합친 후

n의 자리수 + n과 찾은 수와의 차이 를 보았다.

하지만 이렇게 풀이를 하게 되니

예를 들어 n = 1014 이고 고장난 숫자가 0 1 2 3 4 5 6 7 9 이면

가장 가까운 수로 8888을 찾았다.

생각해보면 가장 가까운 수는 888임에도 불구하고.

여러 가지 예시를 토대로 구현하다보니 힘들어서, 문제 분류를 봤는데 brute force문제였다.

채널이 500,000까지 밖에 없으니, 가깝다고 예상한 채널의 최대값은 500,000 * 2 일 것이다.

범위가 1억개 아래니깐 모든 채널을 다 확인해도 됨을 깨달았다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n,m;
bool broken[11];
int result = 999999;
 
int main() {
    scanf("%d %d", &n, &m);
 
    int temp = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &temp);
        broken[temp] = true; //고장난 리모콘 번호키 
    }
    //만약 이동하려는 채널이 100이면 바로 종료
    if (n == 100) {
        printf("0");
        return 0;
    }
 
    //그냥 다른 번호키없이 위아래버튼으로만 이동하려는 채널 갈때 눌러야하는 횟수
    result = abs(100 - n);
    
    for (int i = 0; i < 1000001; i++) {
        int len = 0; //번호키로 누른 횟수
        if (i == 0) {
            //0버튼을 못누르면
            if (broken[0]) len = 0;
            //누를 수 있다면
            else len = 1;
        }
        int temp = i;
        while (temp >0)
        {
            if (broken[temp % 10]) {
                len = 0;
                break;
            }
            temp /= 10;
            len++;
        }
        if (len > 0) {
            // 숫자 누른 횟수 + n과의 차이
            result = min(result, len + abs(i - n));
        }
    }
 
    printf("%d", result);
 
    return 0;
}

결과)