리모컨 1107

문제

접근 방법

1씩 증감하는 경우는 N과의 차의 절댓값을 활용하면 된다.
100으로 확인해 본 뒤 리모컨으로 가능한 숫자 조합을 확인해 보며 N과의 차가 제일 적은 값을 출력하면 된다.

코드

#include <iostream>
#include <queue>
#include <cmath>
#define MAX 1000001
using namespace std;
int N, M, ret = MAX;
int visted[MAX];
bool isBroken[10];
queue<int> q;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0, j; i < M; ++i)
    {
        cin >> j;
        isBroken[j] = true;
    }
    ret = min(ret, abs(N - 100));
    for (int next = 0; next < 10; ++next)
    {
        if (isBroken[next])
            continue;
        visted[next] = 1;
        q.push(next);
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        ret = min(ret, abs(N - cur) + visted[cur]);
        int nextVal = cur * 10;
        for (int i = 0; i < 10; ++i)
        {
            int next = nextVal + i;
            if (isBroken[i] || next == 0 || next >= MAX || visted[next])
                continue;
            visted[next] = visted[cur] + 1;
            q.push(next);
        }
    }
    cout << ret;
    return 0;
}

풀이

1씩 더하거나 빼주어서 값에 도달하려면 너무 많은 시간을 잡아먹는다.
빼기를 활용하면 해결된다.

처음에는 큐에 0을 집어넣고 시작했는데 0이 목표한 값인 경우 최소 1번을 눌러야 하는데 0을 0번 누른 경우로 처리해 줘서 틀렸었다.

이후에도 0에 0을 더하여 무한 루프를 일으키거나 visted 배열에 값을 덮어써 가지고 값에 혼란을 주는 경우도 존재했었다.

일련의 과정을 줄이려고 하다가 큰코다친 경험이라고 생각한다.