[백준] 1107번 : 리모콘

문제

 

---

풀이

 

이 문제 덕분에 가끔은 정말 무식한 방법이 통할 때도 있단 것을 깨달았다.

 

원하는 채널로 가는 방법은 2가지가 있다.

1. +-버튼을 계속 누르기

2. 채널번호 입력후 +-버튼 누르기

 

일단 1번은 간단하다. 목표 채널과 현재 채널의 차이의 절댓값을 구하면 된다.

그리고 2번이 중요한데 난 가능한 모든 채널을 백트래킹으로 탐색해 최솟값을 갱신하려 했다.

 

void backtracking(int pos, int digit) {
    if (digit == 0) //1 1 1 => 2
        return;
    if (pos == digit) {
        int mul = 1, ch = 0;
        for (int i = 0; i < pos; i++) {
            int num = channel.back();
            ch += (num * mul);
            channel.pop_back();
            channel.push_front(num);
            mul *= 10;
        }
        min_click = min(min_click, abs(stoi(N) - ch) + pos);
        return;
    }
    for (int i = 0; i < 10; i++) {
        if (!isBroken[i]) {
            channel.push_back(i);
            backtracking(pos + 1, digit);
            channel.pop_back();
        }
    }
}

5457처럼 네자릿수의 숫자라면 pos==4일 때까지 백트래킹으로 가능한 채널 번호를 입력했다.

그리고 차이를 갱신하는 것이었는데...반례가 있었다.

 

999

1

9

 

이 입력에서 최적 경로는 1000- 즉 5번이다. 위 코드에선 세자리의 수만 탐색하기 때문에 1000을 누를 일이 없다.

        backtracking(0, N.size() + 1); //999 1 9 => 5

그래서 한자리수 더 큰 수도 탐색했다.

 

또 반례가 있었다.

 

11

8

1 3 4 5 6 7 8 9

 

이건 2+++++++++ 즉 10번이 최적 경로이다. 한자리수 더 작은 수도 탐색해야 하는 것이었다.

        backtracking(0, N.size() - 1); //11 8 1 3 4 5 6 7 8 9 => 10

이렇게해서 기적같이 AC를 받긴 했는데 안그래도 시간효율이 좋지 않은 백트래킹을 3번이나 하는건 너무 비효율적인 것 같았다. 그러다가 정말 무식한 방법 하나가 있단 것을 떠올렸다.

 

바로 0채널 부터 가능한 모든 채널을 선형으로 탐색하는 것이었다...

---

소스코드

 

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

bool isBroken[10];
string N;
int min_click;
deque<int> channel;

void backtracking(int pos, int digit) {
    if (digit == 0) //1 1 1 => 2
        return;
    if (pos == digit) {
        int mul = 1, ch = 0;
        for (int i = 0; i < pos; i++) {
            int num = channel.back();
            ch += (num * mul);
            channel.pop_back();
            channel.push_front(num);
            mul *= 10;
        }
        min_click = min(min_click, abs(stoi(N) - ch) + pos);
        return;
    }
    for (int i = 0; i < 10; i++) {
        if (!isBroken[i]) {
            channel.push_back(i);
            backtracking(pos + 1, digit);
            channel.pop_back();
        }
    }
}

int main() {
    int M;

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int input;
        cin >> input;
        isBroken[input] = true;
    }

    min_click = abs(stoi(N) - 100);
    if (M != 10) {
        backtracking(0, N.size() - 1); //11 8 1 3 4 5 6 7 8 9 => 10
        backtracking(0, N.size());
        backtracking(0, N.size() + 1); //999 1 9 => 5
    }
    cout << min_click;
}

일단 백트래킹으로 푼 코드이다. 버리긴 아까우니 적는다.

 

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int MAX = 1000000;
vector<int> broken;

pair<bool, int> isChannel(int x) { //채널 이동 가능 여부, 자릿수
    int cnt = 0;

    if (x == 0) { //0일 때
        if ((find(broken.begin(), broken.end(), x % 10)) != broken.end())
            return make_pair(false, 0);
        cnt = 1;
    }
    while (x != 0) { //부서진 버튼이 있으면 안됨
        cnt++;
        if ((find(broken.begin(), broken.end(), x % 10)) != broken.end())
            return make_pair(false, 0);
        x /= 10;
    }
    return make_pair(true, cnt);
}

int main() {
    int N, M;

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int input;
        cin >> input;
        broken.push_back(input);
    }

    int min_click = abs(N - 100); //그냥 +-
    if (M != 10) { //전부 부서진게 아닐 때
        for (int i = 0; i < MAX; i++) {
            pair<bool, int> result = isChannel(i);
            if (result.first) { //갈 수 있는 채널이면
                min_click = min(min_click, abs(N - i) + result.second); //목표 채널과의 차이 + 자릿수
            }
        }
    }
    cout << min_click;
}

그리고 이게 그냥 선형으로 탐색한 전체 소스코드다.

 

const int MAX = 1000000;
vector<int> broken;

500,000이 최대 입력이라고 해서 1,000,000을 MAX로 잡았다.

broken 벡터엔 부서진 버튼의 정보를 넣는다.

 

    int min_click = abs(N - 100); //그냥 +-
    if (M != 10) { //전부 부서진게 아닐 때
        for (int i = 0; i < MAX; i++) {
            pair<bool, int> result = isChannel(i);
            if (result.first) { //갈 수 있는 채널이면
                min_click = min(min_click, abs(N - i) + result.second); //목표 채널과의 차이 + 자릿수
            }
        }
    }

일단 그냥 +또는 -를 했을 때의 버튼 입력 횟수를 저장했고

모든 버튼이 부서진게 아닌 경우에만 탐색을 시작한다.

 

isChannel 함수는 pair를 반환하는데, 채널 탐색 가능 여부와 자릿수를 담고 있다.

만약 입력 가능한 채널이라면 목표 채널과의 차이의 절댓값을 구하고 여기에 자릿수를 더해 최솟값과 비교한다.

 

pair<bool, int> isChannel(int x) { //채널 이동 가능 여부, 자릿수
    int cnt = 0;

    if (x == 0) { //0일 때
        if ((find(broken.begin(), broken.end(), x % 10)) != broken.end())
            return make_pair(false, 0);
        cnt = 1;
    }
    while (x != 0) { //부서진 버튼이 있으면 안됨
        cnt++;
        if ((find(broken.begin(), broken.end(), x % 10)) != broken.end())
            return make_pair(false, 0);
        x /= 10;
    }
    return make_pair(true, cnt);
}

i 채널을 입력할 수 있는지 확인하는 함수이다.

0번 채널을 입력했을 때를 고려해야 한다. 각 자리를 하나하나 떼어보면서 부서진 버튼이 포함됐는지 확인한다.

부서진 버튼이 있다면 바로 false를 반환한다. 입력 불가 채널이라면 자릿수를 알 필요도 없으니 그냥 0으로 리턴한다.

 

입력 가능한 채널이라면 true와 함께 채널의 자릿수도 반환한다.