백준 1107 ( 브루트 포스 방법)

1107번: 리모컨

과정

• 원하는 채널에 가장 가까운 번호(W) 찾기 → 100에서 W 까지 버튼 수 체크 → (W - 원하는 채널) 해서 +,-수 체크
  이런식으로 계획했다.
• 원하는 채널에 가장 가까운 번호를 어떻게 찾는지가 가장 처음으로 고민한 주제이다.
• 원래는 원하는 채널 번호 기준 가장 가까운 채널번호를 구해서 +, -수만 더 추가하려고 했는데, 생각해보니
  
  100부터 시작이니까 가장 가까운 채널번호가 가장 적게 버튼을 누른다는 보장도 없고,
  
  버튼이 죄다 고장났을 경우, 원하는 채널이 100 일 경우등 이런 예외사항을 예쁘게 정리하게 힘들어서
  
  방법을 바꿨다.
• 일단 무한대 숫자 (대충 백만)들 중 채널을 숫자로 만들 수 있는 얘들을 하나씩 파악하고, 걔네 + +-버튼까지 해서 최소값을 매번 비교(min 함수) 하도록 했다. 
• 솔직히 이방법.. 생각하고 나서도 너무 무식한거 아닌가, 만약 테케가 백만이 아니라 천만이면 어쩌냐 이랬는데 통과도 되고, 다른사람들도 이렇게 풀었다. 이 방법을 브루트 포스방법이라고 부른단다.

코드

#include <iostream>

#include<algorithm>

#include <cmath>

using namespace std;

int N = 0;                 // 이동하려는 채널

int M = 0;                 // 고장난 버튼의 개수

bool buttons[10]; // 리모컨 버튼

bool canMake(int num)

{

    if (num == 0)

    {

        if (buttons[0])

            return true;

        return false;

    }

    while (num)

    {

        if (!buttons[num % 10])

            return false;

        num /= 10;

    }

    return true;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    // bool buttons[10] = {true}; 로 선언할 시 오답처리가 됨;

    fill(buttons, buttons + 10, true);

    cin >> N >> M;

    // 고장난 버튼 파악하기

    for(int i = 0; i < M; i++)

    {

        int num = 0;

        cin >> num;

        buttons[num] = false;

    }

    // +, -만 사용한 횟수

    int answer = abs(N - 100);

    // 숫자 버튼 & +, - 버튼 모두 사용한 횟수

    // 백만개의 채널을 대상으로 가능한지 안한지 파악

    for(int i = 0; i <= 1000000; i++)

    {  

        // 고장난 버튼이 없다면,

        if(canMake(i))

        {

            int move = to_string(i).length();

            move += abs(i - N);

            answer = min(answer, move);

        }

    }

    cout << answer;

}

 

추가적으로 fill(), abs(), min()을 사용하려면,

#include<algorithm>

#include <cmath>

 

을 헤더에 선언해야 한다.