[ 백준 ] 1107번 - 리모컨 (C++)

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

1107번: 리모컨

 

 

[ 문제풀이 ]

 

1. 원하는 채널의 자릿수를 digit 변수에 저장합니다.

 

2. 못 쓰는 숫자를 arr배열에 저장합니다.

 

3. dfs를 통해 만들 수 있는 숫자들을 모두 만듭니다.

 

4. N과 만든 수의 차를 ans와 비교하여 최솟값을 저장합니다.

 

5. 모든 숫자 버튼을 못 쓸 경우가 있기 때문에 level이 0일 때는 cur을 100으로 갱신해줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
using namespace std;
 
int N, M;
int arr[10];
int digit;
int ans = 987654321;
 
void dfs(int level, int cur)
{
    ans = min(ans, abs(N - cur) + level);
 
    if (level == digit + 1)
    {
        return;
    }
 
    if (level == 0) {
        cur = 0;
    }
 
    for (int i = 0; i < 10; i++) {
        if (arr[i] != 1) {
            cur *= 10;
            cur += i;
            dfs(level + 1, cur);
            cur -= i;
            cur /= 10;
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int num;
        scanf("%d", &num);
 
        arr[num] = 1;
    }
 
    if (N == 100) {
        printf("%d", 0);
        return 0;
    }
 
    for (int i = 0; i < 10; i++) {
        if (N < pow(10, i)) {
            digit = i;
            break;
        }
    }
 
    dfs(0, 100);
 
    printf("%d", ans);
}