1107번 : 리모컨

많은 좋은 방법들이 있겠지만 저는 모두 탐색하는 브루트-포스 방식을 택했습니다.

구현하는 방법은 쉽지만 시간과 메모리가 많이 소모되는 방식입니다.

총 3가지 단계로 답을 찾을 수 있습니다.

1. 각 자리의 숫자는 무엇이고 총 몇자리 수인지 파악하기

2. 재귀적으로 값을 찾고(현재의 값과 맞춰야 할 값의 차이를 보면서) 가장 작은 값을 조사하기

3. 값을 비교하기

<첫번째>

총 몇자리 수인지 파악합니다.

각 자리의 숫자를 num[6] 배열에 넣어줍니다.

코드에선 sep() 함수와 sepa() 함수가 이를 처리합니다.

<두번째>

find()함수는 두가지의 인자를 받습니다 : 현재의 값인 n, 그리고 그 n의 자리수를 알려주는 cnt.

현재의 값과 처음에 입력받은 N의 값을 비교해주면서 (둘의 차이) + (n의 자리수인 cnt)의 최솟값을 구합니다.

여기서 이 최솟값은 N보다 하나 작은 자리수일수도 있고, 하나 큰 자리수일수도 있습니다. 각각의 경우를 다 구해야 합니다.

<세번째>

나온 값과 기본값인 100에서 N의 차이를 비교해서 더 작은쪽을 출력합니다.

상당히 많은 반례와 생각지도 못한 부분에서 오류가 발견될 가능성이 매우 많습니다. 저같은 경우는 0의 자리수도 1이라는 것을 간과하여 많은 시간을 날렸습니다...

#include <stdio.h>

int available[10];

int num[6];

int N;

int res = 0xFFFFFF;

int jari;

int sep(int n);

void sepa(int n);

void find(int n, int cnt);

int abs(int a) {

return a >= 0 ? a : -a;

}

int main() {

for (int i = 0; i < 10; ++i) {

available[i] = 1;

}

scanf("%d", &N);

int a;

scanf("%d", &a);

for (int i = 0; i < a; ++i) {

int temp;

scanf("%d", &temp);

available[temp] = 0;

}

jari=sep(N/10)+1;

sepa(jari);

for (int i = 0; i < 10; ++i) {

if (available[i]) {

find(i, 1);

}

}

if (res > abs(N - 100)) res = abs(N - 100);

printf("%d", res);

}

int sep(int n) {

if (n == 0) return 0;

return 1 + sep(n / 10);

}

void find(int n, int cnt) {

if (cnt == jari) {

if (abs(n - N) + cnt < res) res = abs(n - N) + cnt;

}

else if (cnt == jari-1) {

if (abs(n - N) + cnt < res) res = abs(n - N) + cnt;

}

else if (cnt == jari+1) {

if (abs(n - N) + cnt < res) res = abs(n - N) + cnt;

return;

}

for (int i = 0; i < 10; ++i) {

if (!available[i]) continue;

find(10 * n + i, cnt + 1);

}

}

void sepa(int n) {

int temp = N;

for (int i = n - 1; i >= 0; --i) {

num[i] = temp % 10;

temp /= 10;

}

}