알고리즘

[BOJ] 1107 리모컨

졔졔311 2023. 5. 29. 16:45
728x90
반응형

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

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

브루트포스

 

---------------------------------------------------풀이----------------------------------------------------

 

특정 숫자를 누를 경우, 그 숫자에서 +나 -를 이용해서 N까지 이동해야 한다.

따라서, 맨 처음 100번과 N의 차이, 이후 버튼을 눌러 만든 숫자와 N의 차이가 핵심이다.

100번은 처음 숫자이므로 selected는 0이다. 그 상태에서 +/-를 몇 번 눌러야 하는지를 구한다.

이후 버튼을 눌러 만든 숫자 cur은 몇 개를 눌렀는지에 따라 selected가 결정되고, selected+|N-cur|이 눌러야 하는 횟수이다.

재귀함수의 종료 조건은 채널이 최대 500'000까지 있으므로 6번 누를 경우 종료하도록 하였다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

// broken = 0
bool button[10] = {0, };
int ans = INT_MAX;
int N, M;

// 버튼 누른 횟수 selected
void select_buttons(int cur, int selected){
    if(ans > selected + abs(N-cur)){
        ans = selected + abs(N-cur);
    }
    if(N-cur == 0 || selected >= 6){
        return;
    }
    if(selected == 0){
        cur = 0;
    }
    for(int i = 0; i < 10; i++){
        if(!button[i]) continue;
        select_buttons(cur*10+i, selected+1);
    }
}

int main(void){
    FASTIO;
    cin >> N >> M;
    for(int i = 0; i < 10; i++){
        button[i] = true;
    }
    
    for(int i = 0; i < M; i++){
        int tmp;
        cin >> tmp;
        button[tmp] = false;
    }

    select_buttons(100, 0);

    cout << ans << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

시간 제한이 널널해서 쉽게 풀었다.

만약 효율적으로 계산해야했다면, 이 방식 말고 제일 가까운 수를 만드는 방법을 따로 만들어야 했을 것이다.

728x90
반응형