[algorithm] 백준 - 리모컨

brute force 문제이다.

가능한 모든 리모컨 채널을 돌리면서 최소 몇번 눌러지는 지를 체크하면 된다.

 

1. 모든 가능성을 열어두기 위해 중복순열로 자릿수는 0부터 6까지 모든 경우를 구했다.

만약 테스트 케이스가

 

10
2
1 0

이런 경우 자릿수가 1인 9로 이동하는 채널 수가 적기 때문이다.

따라서 모든 자릿수에 대한 채널을 구해야한다.

그리고 이동하려하는 리모컨 채널 - 만들어진 리모컨 + 리모컨을 누른 값 중 가장 작은 값을 구한다.

 

2. 현재 채널인 100에서 이동하고자 하는 리모컨 채널을 뺀 값과 위에서 구한 값을 비교해서 가장 작은 값을 출력한다.

 

코드는 이렇다.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unsigned long answer = 987654321;
void overlapPermutation(vector<int> num, string realNumStr, int target, string numStr){
    if(target == 0){
        answer = min(abs(stoi(realNumStr) - stoi(numStr)) + numStr.length(), answer);
        return;
    }
    for(int i = 0; i < num.size(); i++){
        overlapPermutation(num, realNumStr, target - 1, numStr + to_string(num[i]));
    }
}
int main(void){
    unordered_map<int, bool> removedNumHash;
    int n, removedNum;
    unsigned long channelPassSum;
    string numStr;
    cin >> numStr;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> removedNum;
        removedNumHash.insert({removedNum, true});
    }
    vector<int> numVector;
    for(int i = 0; i < 10; i++){
        if(!removedNumHash.empty()&&removedNumHash.find(i) == removedNumHash.end()){
            numVector.push_back(i);
        }
        if(removedNumHash.empty()){
            numVector.push_back(i);
        }
    }

    if(stoi(numStr) > 100){
        channelPassSum = stoi(numStr) - 100;
    }
    else{
        channelPassSum = 100 - stoi(numStr);
    }
    for(int i = 1; i <= 6; i++){
        overlapPermutation(numVector, numStr, i, "");
    }
    cout << min(channelPassSum, answer);
}