[C++] 백준 - 1107 : 리모컨

문제 링크

로그인

 

 

풀이 )

  모든 버튼이 망가진 경우 '+'나 '-'로만 조작해야하기 때문에 abs(n-100)을 출력하고 종료한다.

 

  고장난 버튼을 제외한 버튼을 v vector에 넣었다.

  답이 나올 수 있는 경우는 다음 3가지 중 하나다.

• n의 길이+1인 채널에서 '-'로 n에 도달
• n의 길이인 채널에서 '-' 또는 '+'로 n에 도달
• n의 길이-1인 채널에서 '+'로 n에 도달

 

  따라서 v에 들어있는 숫자를 이용해서 각 경우의 길이 숫자를 모두 만들어서 최솟값을 갱신한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int tmp = 1e7;

int func(vector<int> v, int len, int channel){
    if(len == 0){
        tmp = min(tmp, abs(channel-n));
        return tmp;
    }

    int ret = 1e7;
    int vLen = v.size();
    for(int i = 0; i < vLen; ++i)
        ret = min(ret, func(v, len-1, channel*10+v[i]));
    return ret;
}

int main(void){
    vector<bool> broken(10);
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int tmp;
        cin >> tmp;
        broken[tmp] = true;
    }
    int ans = abs(n-100);
    if(m == 10){
        cout << ans << '\n';
        return 0;
    }

    vector<int> v;
    for(int i = 0; i < 10; ++i){
        if(!broken[i])
            v.push_back(i);
    }

    int len = 1;
    int tmp = n;
    while(tmp/=10)
        len++;

    if(len > 1)
        ans = min(ans, func(v, len-1, 0)+len-1);
    ans = min(ans, func(v, len, 0)+len);
    ans = min(ans, func(v, len+1, 0)+len+1);

    cout << ans << '\n';
}

 

주의 )

  출력 전 세 줄에 대해서 len-1, len, len+1 순이 아닌 len+1, len, len-1 순으로 갱신할 경우 원하는 답과 다른 결과가 나온다. (func가 반환하는 값이 버튼을 누른 횟수는 반영하지 않기 때문에)