[Baekjoon] 백준 1107번 리모컨

1107번 리모컨 문제 풀이

문제

• 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
  리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
  수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
  수빈이가 지금 보고 있는 채널은 100번이다.

입력

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

출력

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

예제

코드

#include<iostream>
#include<cmath>
using namespace std;

bool broken[10];

int check(int n) {
    if (n == 0) {
        if (broken[0]) {
            return 0;
        }
        else {
            return 1;
        }
    }
    int len = 0;
    while (n > 0) {
        if (broken[n % 10]) return 0;
        n = n / 10;
        len += 1;
    }

    return len;
}

int main() {
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int j;
        cin >> j;
        broken[j] = true;
    }
    int result = abs(n-100);
    for (int i = 0; i <= 1000000; i++) {
        int c = i;
        int len = check(c);
        if (len > 0) {
            int press = abs(c - n);
            if (result > press + len)
                result = press + len;
        }
    }
    cout << result << '\n';
    return 0;
}

해결방법

• 버튼을 최소한으로 눌러서 원하는 채널로 이동해야한다.

• 만약 + , -를 남발하여 이동한 위치의 중복이 발생하면 최소값이 될 수 없다.

• 또한 연산자를 입력하다가 중간에 숫자버튼을 입력하게 되면, 이전에 입력된 것은 모두 초기화 되기 때문에 이런 경우에도 최소값을 구할 수 없다.

• 즉 최소값이 되기위한 조건으로는 숫자 입력이 끝나면 연산자만 입력해야 되며, 연산자는 둘 중 하나만 사용해서 원하는 위치에 도달해야한다.

• 입력할 수 있는 n의 범위는 0 <= n <= 500000이지만 실제로 처음에 이동할 수 있는 채널은 1000000이다.

  1. 300000위치로 이동한고 할 때 1 -> 300000으로 가는 것 보다, 555000 -> 300000으로 가는 방법이 최소이다.
  2. 즉 이동하려는 채널보다 높은 위치에 있을 때 감소하는 범위도 생각해야한다.

• check함수는 이동하려는 채널이 주어졌을 때 리모콘을 클릭하는 횟수를 반환한다.

• 만약 구하려는 수가 0 한자리일 때 고장났다면 0을, 고장나지 않았다면 1을 리턴한다.(고장나지 않았을 때 0을 한 번 입력하여 접근할 수 있다.)

• 0이 아닌 숫자들에 대해서 한 자리씩 고장이 났는지 판별하게된다.

• 3456이라는 숫자가 입력되었을 때 나머지연산을 하게되면 한 자리 수씩 뽑아내어 고장났는지 판별할 수 있다. 이 때 고장나지 않았다면 len을 1씩 증가시켜서 리모컨을 누른 횟수를 반환하게한다.

    int check(int n) {
        if (n == 0) {
            if (broken[0]) {
                return 0;
            }
            else {
                return 1;
            }
        }
        int len = 0;
        while (n > 0) {
            if (broken[n % 10]) return 0;
            n = n / 10;
            len += 1;
        }
  
        return len;
    }

• 처음 시작 위치는 100번이기 때문에 n-100의 절대값을 result에 저장시켜서 연산자 몇 번 눌러야 이동할 수 있는지 저장한다.

    int result = abs(n-100);

• 위치를 비교할 수 있는 범위가 0100만이기 때문에 반복문도 0100만으로 설정한다. 반복문은 0~100만 각각의 위치에서 n위치로 가기 위해서 리모콘을 누르는 횟수를 구한다.

• press는 c-n의 절대값, 즉 내가 누른 번호에서 이동하려는 채널까지 눌러야 하는 연산자의 횟수를 저장한다.

• 마지막으로 result와 press + len, 맨 처음 시작위치 100에서 연산자를 눌러야 하는 횟수를 저장시킨 result와, 내가 누른 번호에서 이동하려는 채널까지 눌러야 하는 횟수 + check함수의 결과값 두 변수를 비교하여 최소값을 result에 저장한다.