[Gold V] 리모콘 - 1107

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

 

고장난 리모콘을 최소로 눌러서 원하는 번호에 도달하는 문제이다.

 

처음에 이 문제를 풀기 위해 여러 방면으로 해보았다.

 

각, 자릿수를 나눠보기도 하고 일치하는 숫자를 최대한 찾은 다음 추가 횟수만 구해보려고 하기도 했다.

 

그런데 전부 예외처리가 힘들어서 불가했다.

 

그 다음으로 브루트포스를 해봤는데 보고나니 시간복잡도가 별 차이가 없었다.

 

만들 수 있는 숫자를 모두 만드는 경우에는 자릿수에서 최대치까지만 모두 점검하면 된다.

 

따라서 시간복잡도는 상수로 사실상 고정되어 있는 것이었다.

 

이때 주의해야할 점은 처음의 채널이 100에 고정되어있다는 것이다.

 

따라서 버튼을 최소로 누르는 것은 + - 버튼 만으로 이동하는 경우도 고려해 줘야하기 때문에 최소 이동횟수를 특수한 기호 등을 통하여 None으로 표시할 것이 아니라 해당 버튼만으로 이동하는 경우로 해야한다는 것이다.

 

입력: 목표 숫자 (target_number), 고장난 버튼 목록 (broken_buttons_list)
초기 채널을 100으로 설정

1. 초기 설정:
   min_button_presses를 초기 채널에서 목표 숫자까지 `+`, `-` 버튼만을 사용하여 이동하는 경우로 설정:
   min_button_presses = abs(target_number - 100)

2. 가능한 모든 숫자에 대해 최소 버튼 누름 계산:
   for number from 0 to 999999:
     a. number를 문자열로 변환
     b. number가 유효한지 검사 (고장난 버튼을 포함하지 않는지 확인):
        - 유효하면:
          i. 숫자를 직접 입력하는데 필요한 버튼 누름 횟수 계산 (숫자의 길이)
          ii. 목표 숫자까지 `+`, `-` 버튼으로 이동하는 버튼 누름 횟수 계산
          iii. 현재 min_button_presses보다 작은 경우 업데이트

3. 최종 결과를 출력: min_button_presses

함수: is_valid_number(number, broken_buttons_list):
  number를 문자열로 변환
  각 자리 숫자가 고장난 버튼인지 검사
  고장난 버튼이 하나라도 포함되어 있으면 False 반환
  그렇지 않으면 True 반환

종료

 

이게 해당하는 수도 코드이다.

 

그리고 아래는 이를 바탕으로 작성한 코드이다.

 

브루트 포스로 하면 금방인데 조금 해매버리고 말았다.

 

#include <iostream>
#include <vector>
#include <string>
#include <cmath> // abs 함수 사용을 위해 포함

#define inf 1e9 // 매우 큰 값을 의미하는 상수
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) // 입출력 속도를 빠르게 하기 위한 설정
using namespace std;

// 고장난 버튼을 추적하는 배열
bool is_broken[10] = { false };

// 숫자가 고장난 버튼을 포함하지 않는지 확인하는 함수
bool is_valid(int num) {
    // 숫자를 문자열로 변환
    string num_str = to_string(num);
    // 각 자리 숫자가 고장난 버튼인지 검사
    for (char digit : num_str) {
        // digit - '0'을 통해 문자 숫자를 정수로 변환하여 고장난 버튼 여부를 확인
        if (is_broken[digit - '0']) {
            return false; // 고장난 버튼이 있으면 false 반환
        }
    }
    return true; // 모든 자리 숫자가 유효하면 true 반환
}

int main() {
    fastio; // 입출력 속도 향상을 위해 fastio 사용
    int target; // 목표 숫자
    int M; // 고장난 버튼의 개수
    cin >> target >> M;

    // 고장난 버튼 입력받기
    for (int i = 0; i < M; i++) {
        int broken_button;
        cin >> broken_button;
        is_broken[broken_button] = true; // 고장난 버튼으로 표시
    }

    // 초기 채널에서 목표 숫자까지 +,-만을 사용해 이동하는 경우의 버튼 누름 횟수
    int min_button_presses = abs(target - 100); // 초기 채널 100에서 +,-만 눌러서 이동

    // 가능한 모든 숫자에 대해 최소 버튼 입력을 찾기
    for (int num = 0; num <= 1000000; num++) { // 0부터 1000000까지 검사
        if (is_valid(num)) { // 숫자가 유효한지 확인
            // 숫자를 직접 입력하는데 필요한 버튼 누름 횟수 (숫자의 길이)
            int button_presses = to_string(num).length();
            // 목표 숫자까지 +,- 버튼으로 이동하는 버튼 누름 횟수 추가
            button_presses += abs(num - target);
            // 현재 min_button_presses보다 작은 경우 업데이트
            if (button_presses < min_button_presses) {
                min_button_presses = button_presses;
            }
        }
    }

    // 최종 결과 출력
    cout << min_button_presses << endl;

    return 0;
}