[BOJ] 백준 1107 리모컨 c++ 코드 / 풀이

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

1107번: 리모컨

(범위 생각 못해서 한번 틀림)

문제해설

 

N으로 이동해야할 채널의 숫자가 주어지고 이후에 사용할 수 없는 버튼의 목록이 입력으로 주어짐

사용 가능 한 버튼과 채널을 하나씩 이동하는 +, -로만 N에 도달해야됨.

우리가 리모컨 쓸 때 처럼 목표 채널을 눌러서 하는 이동과, 채널 위아래 버튼을 통한 이동이 가능한 것

 

문제풀이

 

보고 생각난 건 브루트 포스랑 BFS를 통해 푸는 방법이었음

브루트 포스는 단순하게 그냥 채널 0부터 500,000까지 눌러보면서 버튼을 누르는 횟수를 세며 최소값을 찾는 것

=> 500,000까지만 하면 안됨 n이 500,000이고 사용 가능한 버튼이 1, 5일때 511,111로 이동한 후에 -만 11,111번 눌러서 
이동하는게 최소 이동 횟순데 500,000까지만 반복할 경우엔 도달 불가능함

BFS는 큐에 사용 가능한 버튼들을 넣어서 조합을 시도하고, 이렇게 했을때 N에 도달할 경우 그대로 출력, 안되면 +,-로 이동해서 N까지 이동하는 방식....?

BFS 공부 할 겸 BFS로 구현해 볼 까 하다가 브루트 포스는 너무 명확하게 코드가 나올 것 같아서 그냥 브루트 포스로 구현

 

코드설명

 

시작 채널(100번) 부터 N까지 +와 -로만 도달 가능한 횟수를 기본 값으로 지정 -> abs(n-100)

0~500,000까지 반복하며 현재 i를 숫자 버튼을 통해 이동 할 수 있을 때 버튼을 누르는 횟수 연산

이후 현재 i와 n의 차이만큼 + or -로 이동하는 횟수를 더해 최소값 비교해서 출력값으로 저장

 

ex) n이 5457이고 6 7 8 버튼을 사용할 수 없을 때

사용가능한 버튼 중에 가장 근접한 채널은 5455와 5459임

i가 5455일 때 i를 string으로 변환해서 길이 값을 우선 저장 => string의 길이가 곧 버튼 수이므로

그리고 abs(i-n)만큼의 수를 버튼을 누르는 횟수에 저장 => 5455-5457 = |-2| 이므로 2 => +로 두번 이동 하면 된다는 뜻

 

코드

#include <bits/stdc++.h>
#define PRESET ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

/*
    브루트포스로 구현
    시작 채널(100번) 부터 N까지 +와 -로만 도달 가능한 횟수를 기본값으로 지정 -> abs(n-100) : +와 -로만 n으로 이동가능한 횟수
    0~500,000까지 사용 가능한 버튼으로 해당 채널로 이동이 가능한지 확인
    각 채널마다 N까지 + or -로 이동하여 도달한 횟수 계산
    위 방식들중 최소값을 출력
*/

int n, m;
bool isValid[10]; // 유효 버튼

bool isMove(int num){
    if (num == 0) {
        if (isValid[0]) return true;
        return false;
    }
    while (num) {
        if (!isValid[num % 10]) return false;
        num /= 10;
    }
    return true;
}

int main(){
    PRESET;

    fill(isValid, isValid + 10, true);    
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int idx;
        cin >> idx;
        isValid[idx] = false;
    }

    int result = abs(n-100); // +, -만 사용하여 n까지 채널 이동한 횟수

    for(int i = 0; i <= 1000000; i++){
        if(isMove(i)) {
            int move = to_string(i).length();
            move += abs(i-n);
            result = min(result, move);
        }
    }

    cout << result;
}