[Algorithm] BOJ 1107 리모콘

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

1107 리모콘

---

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

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

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제

---

풀이

---

생각

• 언제나 그랬듯 처음엔 '이거 그냥 쉬운 거 아닌가' 하는 생각으로 접근했다... '이거 그냥 근접한 수 구해서 오차 구하면 되는 거 아닌가...'하는 생각
  • 개소리
• 처음엔 원하는 채널의 숫자를 가져와서 리모콘으로 갈 수 있느냐 없느냐를 따지고 제일 근접한 수를 찾아보자 했는데, 문제가 너무 많았다.
  • 누를 수 없는 번호가 있으면, 어떻게 할 것인가? 가장 가까운 번호?
  • 자릿수도 생각해야 했다. 10을 가야하는데, 1과 0을 사용 못한다면 9로 가야하므로...
• 결국, Bruteforce로 풀어야 함을 깨달았다.
  • 구글신의 힘을 받아 깨달았다.
  • 채널 100번(시작)에서 리모콘으로 갈 수 있는 모든 경우를 구하고, 목표채널로 이동해보자.
• +/-로 가는게 빠를까? 숫자버튼으로 누르는게 빠를까?
  • 채널 102번을 가고자 한다. --> +/- 2번 or 숫자버튼 3번
  • 채널 104번을 가고자 한다. --> +/- 4번 or 숫자버튼 3번
  • 즉, 목표 채널마다 다르다는 것. 둘 다 구해서 비교해봐야 한다는 것.
• 목표 채널은 500,000이 최대이다. 하지만 채널은 무한대 !
  • 채널 500,000번을 가고자 한다. 근데 0, 4, 5, 9 버튼이 고장났다.
  • 100에서 +버튼으로 접근? OR 611,111에서 -로 접근?
  • 당연히 후자다. 즉, 500,000을 넘어선 채널에서 접근하는 방법도 생각해봐야 한다.
• 최악의 수를 생각하면, 1,000,000번에서 접근하는 것이 최악의 수가 될 것이다.
  • (정확히는 999,900이지 않을까?)
  • 100 -> 500,000 OR 1,000,000 -> 500,000
  • 결국, 모든 경우를 볼 때는 0 ~ 1,000,000 까지 확인해야 한다는 것.

방법

• 현재 채널(100)과 목표 채널의 차(A)를 구한다.
  • +/- 버튼만 눌러 목표 채널로 간 경우
• 1 ~ 1,000,000를 순회한다.
  • 현재 채널은 리모콘 숫자 키로 바로 이동할 수 있는가?
  • 가능하다면, 숫자 키로 이동한 후 +/-를 통해 목표 채널로 이동하자.
  • 목표채널까지 이동하는데 클릭한 버튼 수(B)를 구한다.
• A와 B를 비교하자.
  • B가 더 작다면, 이번 조합으로 가는 것이 더 적은 클릭 수라는 것. 고로, 결과를 B로 업데이트 !
• 위 과정이 끝나면 목표 채널로 가는 최소 클릭 수를 구할 수 있다.

유의

• 1,000,000까지 순회를 해야한다는 것.
  • 500,000보다 큰 채널에서 접근하는 것이 어느 때는 더 최소 클릭일 수 있다는 것을 생각.
• 숫자 버튼과 +/- 버튼을 조합한다는 것.
  • 숫자로 갈 수 있으면 먼저 이동하고, +/-로 가자.

---

코드

---

#include <iostream>
#define bb ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int n, m, ans, cnt, start = 100;
bool broken[10];

int moveRemote(int num) {
    // 0인 경우, 따로 잡아준다.
    if (num == 0) {
        if (broken[num]) return -1;
        return 1;
    }

    // 숫자로 이동이 가능한가?
    int len = 0;
    while (num > 0) {
        if (broken[num % 10]) return -1;
        len++;
        num /= 10;
    }
    return len;
}

int main() {
    // input
    int tmp;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> tmp;
        broken[tmp] = true;
    }

    // 가고자 하는 채널과 현재 채널이 같으면 그냥 종료
    if (n == start) {
        cout << 0 << '\n';
        return 0;
    }

    // Process
    ans = abs(n - start);    // +/-로만 이동하는 경우
    for (int i = 0; i < 1'000'000; ++i) {
        cnt = moveRemote(i);    // 숫자버튼으로 가능한가?
        if (cnt > 0) {            // 숫자버튼으로 이동가능하면
            cnt += abs(n - i);    // 숫자버튼으로 이동하고, +/- 이동
            ans = ans > cnt ? cnt : ans;    // 값이 더 작으면, 업데이트
        }
    }

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

---

느낀점

• 한 약 2주만에 다시 알고리즘을 푼 것 같다.
  • 뭔가 꾸준히 해야하는데, 삶의 힘듦이 너무 크게 왔다.
• 간단해보여도 왠지 모르게 개고생 했다. 너무 오랜만에 풀어서 그런가...
  • 언제나 그렇듯, 급히 생각하지 말자.

---

참조

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