[백준] 1107 리모컨(C++)

 

문제 URL:

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

위 문제는 m개의 리모컨 버튼이 고장났을 때 원하는 채널까지 최소한으로 이동하기 위해서는 몇 번 움직여야 하는지를 출력하는 문제로 브루트포스 알고리즘을 이용하는 문제이다. 

 

먼저 +/-로만 갈 수 있는 횟수를 최솟값으로 잡아놓고 check()함수를 통해 현재 숫자가 고장난 버튼이 포함되지 않은 숫자일 경우에 최솟값과 이동 횟수 비교를 진행한다. 이때, 500,000이 넘는 숫자에서 -버튼을 통해 내려오는 경우도 있기 때문에 브루트포스를 진행하는 숫자는 1,000,000으로 잡아준다.

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> dp;
vector<bool> btn(10,false);  // 0~9까지의 리모컨 버튼. true:고장남, false: 고장 안 남

bool check(int now){  // 고장난 버튼인지 확인. 고장 났다면 return false
    string s = to_string(now);
    for(int i = 0; i <s.length();i++){
        if(btn[s[i] - '0'])
            return false;
    }
  
    return true;
}

int main(){
    int n, m;
    cin >> n >> m;

    int num;
    for(int i = 0; i < m; i++){
        cin >> num;
        btn[num] = true;
    }

    int minimum = abs(n - 100);  // +/-버튼으로만 목적 채널까지 도달할 경우
    for(int i = 0; i <= 1000000; i++){  // 
        if(check(i)){  // 숫자에 고장난 버튼이 포함되어 있지 않은 경우에만 비교 진행
            int tmp = abs(n - i) + to_string(i).length();
            minimum = min(minimum, tmp);
        }
    }

    cout<< minimum;

    return 0;
}

참고: https://yjios.tistory.com/8