1107번

1107번 - 리모컨

처음에 어떻게 풀어야할까 고민을 많이 했다. 완전 탐색이란 걸 알았는데도, 어떤 식으로 구현할지 몰랐다.

그러다가 일단, 두가지 케이스로 생각했다.

첫번째, +와 - 만을 이용해서 움직이는 경우.

두번째, 특정숫자로 간 후, +와-만을 이용해서 움직이는 경우.

하지만 특정 숫자로 어떻게 가야할지에 대해서 감이 잡히지가 않았다. 그러던 중 내가 숫자로 가기 보다는

그 목적 숫자를 +1, -1 하면서 갈 수 있는 가장 빠른 경우 ( 그래야 특정 숫자로 이동 후, +와 - 연산을 최소화 할 수 있다.) 를 찾고

그 이후에 그 숫자의 자릿수를 더해주면 된다고 생각했다.

x는 목적지 기준으로 - 를 해주고, y는 목적지를 기준으로 +를 해주면서 가장 가까운 값을 찾았다. 

만약 리모컨의 모든 숫자가 고장난 경우에는 +,- 만을 이용할 수 밖에 없어서 그 부분을 while문의 조건으로 입력했다.

canGo 함수에서는 갈 수 있는지 판단하고, 갈 수 있다면 몇자리 수인지 return 하도록 구현하였다.

풀면서 생긴 문제점

1.

문제를 풀면서 x,y 를 따로 while문으로 쓰고, 모든 리모컨 숫자가 고장난 경우를 생각 못해서 시간초과가 발생했었다. 

2.

canGo 에서 n==0일때 설정을 해주지 않아서, 0이 들어왔을 때 제대로 작동하지 않았었다.

<정답 코드>

 

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int canGo(int n,const bool *broken)
{
    if (n == 0)
    {
        if (broken[0])
        {
            return 987654321;
        }
        else
        {
            return 1;
        }
    }
 
    int ans = 0;
 
    while (n != 0)
    {
        if (broken[n % 10])
        {
            return 987654321;
        }
 
        n /= 10;
        ans += 1;
    }
 
    return ans;
    
}
int updown(int start, int dest)
{
    return abs(start - dest);
}
 
int main()
{
    int N, M, now = 100;
    bool broken[10];
    memset(broken, false, sizeof(broken));
 
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        broken[tmp] = true;
    }
    int minn = updown(now, N);
 
    int x = N;
    int y = N;
 
    while (M!=10)
    {
        int cnt = canGo(x, broken);
        int cnt1 = canGo(y, broken);
        
 
        if (cnt != 987654321)
        {
            cnt += updown(x,N);
            minn = min(minn, cnt);
            break;
        }
 
        if (cnt1 != 987654321)
        {
            cnt1 += updown(y, N);
            minn = min(minn, cnt1);
            break;
        }
 
        x -= 1;
        y += 1;
 
        if (x < 0)
        {
            x = 0;
        }
    }
 
 
    cout << minn << endl;
    return 0;
}