[BOJ 1107 // C++] 리모컨

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1107번 문제인 리모컨이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1107

1107번: 리모컨

처음에는 이 문제를 시도할 때 다음과 같은 알고리즘을 구상했었다.

 

1) 만들려는 수까지 +나 -만을 이용하여 필요한 버튼을 누르는 횟수를 구해 저장한다.

2) 만들려는 수보다 크거나 같은 수 중 숫자버튼으로 누를 수 있는 가장 작은 수를 구한다. 구한 수를 입력하는 횟수와 구한 수에서 만들려는 수까지 - 버튼을 눌러야하는 수를 합해 저장한다.

3) 만들려는 수보다 작거나 같은 수 중 숫자버튼으로 누를 수 있는 가장 큰 수를 구한다. 구한 수를 입력하는 횟수와 구한 수에서 만들려는 수까지 +버튼을 눌러야하는 수를 합해 저장한다.

4) 1, 2, 3에서 구한 수중 최솟값을 출력한다.

 

2-1) 큰 자릿수부터 숫자를 읽어내려온다. 누를 수 없는 자릿수를 만나면, 그 자릿수에 1씩 더해 이 수보다 큰 자릿수의 숫자들이 다 누를 수 있는 수가 되게끔 만든다. 아랫자리수들을 전부 누를 수 있는 가장 작은 숫자로 바꾼다.

2-2) 큰 자릿수부터 숫자를 읽어내려온다. 누를 수 없는 자릿수를 만나면, 그 자릿수에서 1씩 빼서 이 수보다 큰 자릿수의 숫자들이 다 누를 수 있는 수가 되게끔 만든다. 아랫자리수들을 전부 누를 수 있는 가장 큰 숫자로 바꾼다.

 

 

그러나, 이 문제의 숫자의 범위가 50만 이하여서 이런 구체적인 알고리즘이 필요할 것 같지 않았고, 처음에 누를 채널 숫자 후보로 가능한 모든 숫자를 탐색하는 방식으로 방향을 틀었다.

 

제출한 알고리즘은 다음과 같다.

 

1) 만들려는 수까지 +나 -만을 이용하여 필요한 버튼을 누르는 횟수를 구해 저장한다.

2) 0부터 100만까지 숫자 가운데 누를 수 있는 숫자들을 구해 (숫자의 자릿수) + (숫자-만들려는숫자) 들의 최솟값을 구한다.

3) 1과 2의 최솟값을 출력한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
using std::min;

bool usable[10] = { true, true, true, true, true, true, true, true, true, true };

int press(int n, int i) {
    int cnt = abs(n-i);
    if (i == 0) { // 예외처리 - 0의 경우
        if (!usable[0]) return 1000000;
        cnt++;
    }
    while (i > 0) { // 0의 경우 반복문을 들어올 수 없으므로 예외처리
        int x = i % 10;
        if (!usable[x]) { // 누를 수 없는 자리가 포함되어있다면
            return 1000000; // 최솟값이 될 수 없는 불가능한 값을 리턴
        }
        cnt++; // 자릿수마다 버튼 누르는 횟수가 1씩 증가
        i /= 10;
    }
    return cnt;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int temp;
        cin >> temp;
        usable[temp] = false;;
    }
    int ans = abs(n - 100);
    for (int i = 0;i < 1000000;i++) { // 모든 가능한 숫자 시도
        ans = min(ans, press(n,i));
    }

    cout << ans;

    return 0;
}