백준 1107 리모컨 - 브루트포스 - c++

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

1107번: 리모컨

우선 이 문제를 풀기 전 내 아이디어(브루트 포스 첫 문제다.)

1. 고장난 리모컨 버튼들을 입력받아서, 0-9에서 뺀다. 그럼 잘 작동하는 리모컨 버튼만 입력을 받을 수 있을 것.(arr나 벡터에 저장하기.)
2. 가장 큰 자리수부터 검사해서, 배열에 있는지 없는지 확인. 없으면 차이의 절댓값이 제일 작은 녀석을 골라서 다 밑의 자리수가 5 이상 이하인지 또 검사해서 판단해서 고르기.
3. 이렇게 고른 숫자랑 +- 버튼 횟수를 더한다음에, 100에서 +- 버튼 누른거랑 확인하기.

로 일단 구성을 짰다. 

 

이렇게 처음엔 무조건 차이를 최소화하는 방식으로 접근하는 것이 맞겠다고 판단을 했었는데(그리디 방식)

잘못 되엇음을 아래 예제를 통해 알 수 있었다. 출처: https://blog.naver.com/PostView.nhn?blogId=occidere&logNo=221354997206&categoryNo=49&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView

[백준] 1107 - 리모컨

1555

8 0 1 3 4 5 6 7 9

위 예시에선 버튼을 2, 8을 사용할 수 있다. 3가지 접근 방식을 적용해보면 아래와 같다.

(1) 기본값에서 + 버튼으로 접근
  * 1555 - 100 = 1,455 번
(2) 수학적으로 버튼을 1개씩 눌러가며 최소값을 선택하는 식으로 접근
  * 1과 차이가 최소인 버튼인 2를 선택 (1회)
  * 5와 차이가 최소인 버튼인 2를 선택 (2회)
  * 5와 차이가 최소인 버튼인 2를 선택 (3회)
  * 5와 차이가 최소인 버튼인 2를 선택 (4회)
  * 667 번 -버튼 클릭 (2222 - 1555)
  * 4번 + 667번 = 671번
(3) 정답 케이스
  * 888 번호 선택 (8을 3번 누름)
  * 667번 +버튼 클릭 (1555 - 888)
  * 3번 + 667번 = 670번

[출처] [백준] 1107 - 리모컨|작성자 occidere

 

 

그래서 포기하고 무식한 브루트포스 방식을 사용하는 것이다!

수학적으로 탐색하지 않아도 되는 boundary는 제끼면서 풀어도 나쁘지 않을 것 같다만 

가장 간단하게 할 수 있는 방법은 (경우의 수가 많아봤자 0~1000000 백만가지 밖에 안되기 때문에)

브루트 포스로 하는 방식이 제일 편한 방식인 듯하다.

 

check(int n)은 어떤 숫자가 버튼을 눌러서 반환 될수 있는지 여부를 확인함.

0이 나오면 숫자 n에는 고장난 버튼이 있는거고, 일반 숫자가 반환되면 그 n에는 고장난 버튼 없이 누를 수 있는 것이며 그 숫자의 길이가 반환됨. 결국 그 숫자 길이만큼 리모컨 버튼을 눌러야 하니까.

 

코드를 보면 다음과 같다. 브루트포스는 코드 짜는게 아직은 익숙하지 않아서 AC받은 코드들을 보고 공부하는 입장이다 지금은.

#include <iostream>
#include <cmath>
using namespace std;
bool brokenbutton[10];
 
int check(int n){
    if(n==0){
        if(brokenbutton[0])
            return 0;
        else
            return 1;
    }
 
    else{
        int len=0;
        while(n>0){
            if(brokenbutton[n%10])
                return 0;
            n /=10;
            len+=1;
        }
        return len;
 
    }
 
}
 
int main(void){
    int channel,m;
    cin>>channel>>m;
    for(int i=0; i<m; i++){
        int j;
        cin>>j;
        brokenbutton[j]=true;
    }
 
    int result = abs(100-channel);
    for(int i=0;i<=1000000; i++){
        int len = check(i);
        if(len>0){
            int press = abs(channel-i);
            result = min(result,press+len);
        }
    }
    cout<<result;
}