백준 1107_리모컨

문제 링크

문제한줄요약

고장난 버튼을 제외하고 최소한의 버튼을 눌러 시작번호에서 해당 번호로 이동시킨다.

내가 생각한 조건

시작 번호와 해당 번호가 같으면 0을 출력한다. 그리고 고장난 버튼이 0개일 때는 버튼을 입력받지 않게 처리한다.
최소한의 버튼 횟수를 구하기 위해 (해당 번호) - (버튼을 눌러 만들 수 있는 수)가 최소인 것, 버튼을 눌러 만들 수 있는 수 2가지의 기준을 세워 최소값을 구하려 했었다.
그리고 다른 테스트 케이스에서 버튼을 눌러 만들 수 있는 수들의 합/차라는 기준을 추가해야 한다는 것을 알고 구현 과정에 문제가 생겨서 링크를 참고했다.

작성한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int MAX = 1000000 + 1;
const int INF = 987654321;
int n, m;
 
vector<int> v;
 
int fromStart()
{
    return abs(n - 100);
}
 
bool possible(int n)
{
    if(n == 0)
    {
        if(find(v.begin(), v.end(), 0) == v.end())
            return true;
        else 
            return false;
    }
 
    while(n)
    {
        if(find(v.begin(), v.end(), n % 10) != v.end()) 
            return false;
        n /= 10;
    }
    return true;
}
 
int length(int n)
{
    if(n == 0) return 1;
    int res = 0;
    while(n)
    {
        n /= 10;
        res++;
    }
    return res;
}
 
int ChangeAll(void)
{
    int res = INF;
    int num = 0;
 
    for(int i = 0; i < MAX; i++)
    {
        if(possible(i))
        {
            int click = abs(n - i);
            if(res > click)
            {
                res = click;
                num = i;
            }
        }
    }
    return res + length(num);
}
 
int main()
{
    
    cin >> n >> m;
 
    for(int i = 0; i < m; i++)
    {
        int cnt;
        cin >> cnt;
        v.push_back(cnt);
    }
 
    cout << min(fromStart(), ChangeAll()) << '\n';
    return 0;
}

피드백

나는 처음에 무조건 수학적 공식을 이용해서 구하려고 했는데 완전 탐색이 더 효율적인 것을 보고 당황스러웠다. (링크 참조) 시간복잡도를 생각하면서 문제를 풀어야 할 것 같은 생각이 든다.

한줄평

무조건 공식을 만들려고 하지 말고 완전탐색을 하는 방법도 고민해 보자.