#1107번 리모컨 (C++)

문제 링크 : www.acmicpc.net/problem/1107

1107번: 리모컨

문제 풀이는 다음과 같다.

1. +-버튼만을 이용해서 채널을 이동하는 경우

    ans = n-100; // 1. +-버튼만 눌러서 움직이는 경우
    if(ans<0) ans = -ans;

(1) 목표채널 - 100(시작지점)을 해준다. 

(2) 만약 (1)의 값이 음수일 경우, 절대값으로 전환해준다.

 

2. 숫자버튼과 +-버튼을 같이 이용하여 채널을 이동하는 경우

(1) Brute Force를 이용해 값을 구해준다. 

이때 for문의 최대범위값은 1,000,000인데, 채널의 최대범위인 500,000의 정확히 2배이다. 

2배로 설정한 이유는 다음과 같다. 

만약 499,999이 목표 채널인데, '9','4','8','0'버튼이 사용 불가능일 경우, 511,111에서 -버튼을 눌러주는게 빠른 지름길이기 때문이다.

(2) 리모컨 버튼으로만 이동 가능한 버튼들을 구한 뒤, +-을 누르는 횟수를 함께 더해주어서 저장된 ans와 비교하여 더 작은 값을 ans로 저장해준다.

 

2번의 경우 아래 코드의 주석을 보면 더 쉽게 이해가 된다.

 

#include <iostream>
using namespace std;

bool ch[10] = {false,};

int possible(int c){
    if(c==0){
        if(ch[c]) return 0;
        else return 1;
    }
    int len = 0;
    while(c>0){
        if(ch[c%10]) return 0;
        c/=10;
        len++;
    }
    return len;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n=0, m=0, ans=0, temp=0;
    cin >> n;
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> temp;
        ch[temp] = true;
    }
    ans = n-100; // 1. +-버튼만 눌러서 움직이는 경우
    if(ans<0) ans = -ans;
    for(int i=0; i<=1000000; i++){ // 2. 숫자와 +-버튼을 같이 누르는 경우
        temp = i;
        int len = possible(temp);
        if(len>0){
            int press = temp-n; // 현재 지점 - 목표 지점 = 눌러야하는 +-버튼 횟수
            if(press<0) press = -press; // 음수일 경우 절대값으로 바꿔준다
            if(ans>len + press) ans = len + press; // len + press = 숫자 버튼 누르는 횟수 + 눌러야하는 +-버튼 횟수
        }
    }
    cout << ans << "\n";
    return 0;
}