[BOJ 1107] 리모컨(C++)

리모컨(Gold 5)

문제

전체 문제 보기

1107번: 리모컨

접근법

이번 문제는 완전 탐색(Brute Force)으로 풀 수 있는 문제입니다. Brute Force 문제를 접했을 때 Brute Force로 풀수 있는지 가늠해 보고 판단하는 것이 중요합니다. 이번 문제는 다음과 같이 탐색하면 충분히 완전 탐색이 가능합니다.

• 0번 채널 ~ 1,000,000 채널까지 탐색을 진행
• 각 채널이 고장나지 않은 버튼들로 만들 수 있는지 확인
  • 만들 수 있는 채널이라면, 해당 채널에서 +,-을 활용해서 목표까지 이동거리 계산
  • 입력 횟수 최솟값 갱신

위와 같은 방법으로 \(O(n)\) 회 만에 탐색을 마칠 수 있습니다. 최대 1,000,000번만 탐색하면 되기 때문에 Brute Force로 충분히 풀 수 있습니다.

전체 구현코드

목표 채널이 0번인 경우와, 목표 채널이 100번인 경우에 대한 반례를 주의해야 합니다. 목표 채널보다 큰 수에서 -버튼으로 접근할 수 있기 때문에 최대 N + 500'000번 까지 탐색해야 합니다.

#include <iostream>
#include <algorithm>
#include <array>
#define endl '\n'
using namespace std;
const int INF = 100'000'000;

bool IsValid(int n, array<int, 10>& button, int& len)
{
    len = 0;
    do
    {
        int a = n;
        n /= 10;
        a -= n * 10;
        if (button[a] == false) return false;

        len++;
    }while (n > 0);

    return true;
}
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, M; //  N (0 ≤ N ≤ 500,000), M (0 ≤ M ≤ 10)
    cin >> N >> M;

    array<int, 10> button{};
    button.fill(true);

    while (M--)
    {
        int b;
        cin >> b;
        button[b] = false;
    }
    int minInput = INF;
    for (int i = 0; i <= N  + 500'000; ++i)
    {
        int len{}; // i의 길이. IsValid 함수에서 계산됨.
        // 고장나지 않은 버튼으로 만들 수 없는 수라면 continue
        if (IsValid(i, button, len) == false) continue;

        const int input_cnt = abs(N - i) + len;
        minInput = min(minInput, input_cnt);
    }
    // 채널 100에서 움직이는 경우 계산
    minInput = min(minInput, abs(N - 100));
    cout << minInput;
    return 0;
}