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

 

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

 

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

1107번: 리모컨

---

 

해결전략

 

구현, 브루트포스 Brute Force

 

---

 

정답 코드

 

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int n, m;
set<int> broken;

// num에 고장난 버튼이 포함되어 있는지 확인하는 함수
bool isPossible(int num) {
    if (num == 0) {
        return broken.find(0) == broken.end();
    }
    while (num) {
        if (broken.find(num % 10) != broken.end()) {
            return false;
        }
        num /= 10;
    }
    return true;
}

// 숫자 num의 길이를 반환하는 함수
int getLength(int num) {
    if (num == 0) {
        return 1;
    }
    int len = 0;
    while (num) {
        len++;
        num /= 10;
    }
    return len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    int input;
    for (int i = 0; i < m; i++) {
        cin >> input;
        broken.insert(input);
    }

    int answer = abs(n - 100); // 처음에 +, - 버튼만 사용하여 채널 이동하는 경우를 answer로 설정
    
    for (int i = 0; i <= 1000000; i++) // 가능한 모든 채널을 확인 (0 ~ 1,000,000)
    {        
        if (isPossible(i)) // 고장난 버튼이 없는 채널인 경우
        {
            int len = getLength(i); // 채널 번호의 길이 계산
            
            answer = min(answer, abs(n - i) + len); // 기존 answer와 비교하여 최소 버튼 클릭 횟수를 찾음
        }
    }

    cout << answer << "\n";

    return 0;
}

 

 

 

코드에서 0부터 1,000,000까지 검사하는 이유는 '채널을 직접 입력'하는 경우를 고려하기 위함이다.

직접 채널을 입력하는 경우, 버튼을 누르는 횟수는 채널 번호의 자릿수와 동일하다. 예를 들어, 500,000 채널로 이동하려면 6번의 버튼을 누르면 되지만, 500,000에서 + 또는 - 버튼을 사용해 1 채널 이동하려면 최소 500,000번 버튼을 눌러야 한다.

하지만 문제의 조건에서 채널은 500,000까지라고 했음에도 1,000,000까지 검사하는 이유를 궁금해하다면, 이는 '버튼을 눌러 채널을 직접 입력한 후 + 혹은 - 버튼을 눌러 원하는 채널에 도달하는 경우'를 고려하기 위함이다.

예를 들어, 500,000 채널로 이동하려는 상황에서 4번 버튼이 고장났다고 가정하자. 이 경우에는 500,000을 직접 입력할 수 없다. 하지만 499,999나 500,001과 같이 500,000 주변의 채널을 직접 입력한 후 + 또는 - 버튼을 눌러 500,000 채널에 도달할 수 있습니다. 이런 경우를 고려하기 위해 1,000,000까지 검사하는 것이다.

즉, 이 코드는 '직접 입력'과 '+, - 버튼 사용'을 결합한 모든 경우의 수를 고려하고 있다. 이렇게 모든 가능성을 검사함으로써 문제의 정답, 즉 원하는 채널에 도달하기 위한 최소 버튼 클릭 횟수를 정확히 찾아낼 수 있다.

 

---