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

www.acmicpc.net/problem/1107

1107번: 리모컨

브루트 포스(완전 탐색) 유형의 문제입니다.

answer의 초기값을 '숫자 버튼을 누르지 않았을 경우', '+/- 버튼만을 누른 경우' 두가지를 고려하여 설정해주고, 0번 채널부터 1000000번 채널까지 차례대로 N번 채널로 가기 위해 숫자 버튼을 몇번 누르는지 확인합니다. 확인 후 고장난 버튼이 있으면 0을 리턴하고 고장난 버튼이 없으면 개수를 리턴합니다. '현재 채널 - N번 채널'의 절대값과 방금 구한 개수를 더하여 기존의 answer과 어떤게 더 작은지 계속해서 비교하여 최소값을 구해내면됩니다.

이때 입력의 최대값이 500000인데 1000000까지 탐색을 하는 이유는 문제의 예제 입력 3번과 같은 경우 때문입니다.

 

500000

8

0 2 3 4 6 7 8 9

 

위와 같이 입력이 들어왔을 때, 숫자 버튼을 6번 눌러 511111 채널로 가고, - 버튼을 11111번 누르면 가장 버튼을 적게 누르고 목표 채널로 이동할 수 있는데, 이 때 채널의 범위가 500000이라면 위의 결과를 얻을 수 없습니다.

 

#include <iostream>
using namespace std;

bool broken[11];

int howManyPush(int ch) {
    int cnt = 0;
    // 밑의 while문의 조건 때문에 ch가 0일 때 항상 0이 리턴되므로 따로 예외처리
    if(ch == 0) return broken[ch] ? 0 : 1;
    // 채널의 자리 수 == 숫자 버튼을 누른 수
    while(1) {
        if(ch == 0) return cnt; 
        if(broken[ch % 10]) return 0; // 고장난 버튼이 있으므로 숫자 버튼으로 갈 수 없음
        cnt++;
        ch /= 10;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin>>n>>m;
    while(m--) {
        int button;
        cin>>button;
        broken[button] = true;
    }
    
    int answer = abs(n - 100); // 숫자 버튼을 누르지 않았을 경우, +/- 버튼만을 누른 경우
    // 0번 ~ 1000000번을 이동하는데 숫자 버튼을 몇번 눌러갈 수 있는지 확인
    for(int ch = 0; ch <= 1000000; ch++) {
        int cnt = howManyPush(ch);
        if(cnt > 0) {
            int updown = abs(ch - n); // 숫자 버튼으로 이동 후, +/- 버튼만을 누른 수
            answer = min(answer, updown + cnt);
        }
    }
    cout<<answer;
}