[BAEKJOON] 1107_리모컨_C언어

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

풀이

모든 경우의 수를 다 해보는 부르트 포스문제이다. 모든 경우의 수를 다 계산하여도 제한시간을 초과하지 않는다.

1. 여기서는 100에서 + - 버튼으로 원하는 채널까지 이동하기 위해 누른 버른의 회수 k.

2. 고장난 버튼때문에 원하는 채널에서 가장 가까운 수까지 버튼을 x번 누른수 + - 버튼을 누르는 y번의 합.

k와 x+y의 값을 비교하여 더 작은 값을 출력하면된다.

여기서 k와 x+y는 항상 양수여야 되므로 음수이면 if문을 사용하여 양수로 바꾸어준다.

위의 1번에서 말한 k=원하는 채널 - 100;

x는 예로 5000이면 5를 한 번 0을 3번 눌러야되므로 4이다.

y는 목표값이 4800이고 사용 가능한 버튼으로 목표값에 가장 가까지 갈 수있는 채널이 5000이면

y=5000-4800이다.

2번에서 말한 x+y=4+200=204이다.

-------

여기서 수빈이가 이동하고자하는 채널은 50000이하이므로 고장난 버튼을 고려하면 최대 100000까지 탐색해주어야한다.

-------

탐색하는 함수는 검사하고자 하는 값이 0이면 고장난 값이 0인지, 채널이 0인지 고려를 우선적으로 해주며,

그 후 %와 /연산을 통해 탐색하는 수에 고장난 버튼의 수가 있으면 0을 반환하고, 고장난 버튼이 없이 사용가능한 버튼들로 이루어진 수로이루어져 있으면 해당 수의 길이를 반환하도록 함수를 만들었다.

작성한 코드

#include <stdio.h>
int broken[11];
int num_1,num_2,num, N,goal,min=1000000,length,l;
int check(int);
 
int main()
{
    scanf("%d %d",&goal,&N);
    num_1 = goal - 100;//+ -로만 이동하는 회수 k
    if (num_1 < 0)num_1 = -1 * num_1;
 
    for (int i = 0; i < N; i++)//고장난 버튼 입력
    {
        int k;
        scanf("%d",&k);
        broken[k] = 1;
    }
 
    for (int i = 0; i < 1000001; i++)
    {
        length=check(i);
        if (length)
        {
            int k = goal - i;
            if (k < 0) k = k*-1;
            if (k < min)
            {
                min = k;
                l = length;
            }
        }
    }
    num_2 = min+ l;//x+y
 
    printf("%d",num_1<num_2?num_1:num_2);//작은 값 출력
 
    return 0;
}
 
int check(int k)//해당 수로 이동가능한지를 판별
{
    int length = 0;
    if (k == 0) {
        return broken[0] ? 0 : 1;
    }
    while (k)
    {
        length++;
        if (broken[k % 10]) return 0;
        k /= 10;
    }
    return length;
}