BOJ(리모컨) 12101

작성일 | In
  • 브루트포스 문제
  • 모든 경우의 수를 다 따져봐야 함
  1. for문 이용
  2. 순열 이용하기
  3. 재귀 이용하기
  4. 비트마스크 이용하기

리모컨

  • 리모컨에는 버튼이 0~9까지 숫자, +와 -가 있다.
  • +를 누르면 현재 보고 있는 채널에서 +1만큼 이동
  • -를 누르면 -1된 채널로 이동
  • 채널 0 에서 -를 누른 경우에는 채널이 변하지 않고 채널은 무한대만큼 있다.
  • 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는가?

  • 지금 보고 있는 채널은 100번이다.

  • 입력
  • 첫째 줄 : N으로 이동하기 위한 채널.
  • 둘째 줄: 고장난 버튼 수

  • 셋째 줄 : 고장난 버튼이 주어짐

  • 예를 들어 5456으로 이동하고 싶으면 5456을 차례로 누르면 된다.

  • 그렇게 되면 4번만에 이동이 가능하다

  • 이 문제가 어려워지는 이유는 일부 숫자 버튼이 고장났다는 것이다.
  • 만약 6번 버튼이 고장이 났다면 5456을 눌를 수 없다.
  • 이런 경우라고 한다면, 5455에 이동한 뒤, +1을 해주거나, 5457을 이동한 뒤 -1을 눌러야한다
  • 위 방법은 모두 다섯 번이다.

  • 최소를 구해야 한다

  • 최소를 구하는 성질은 무엇인가 ?
  • 6,7,8이 고장났고 5457로 이동하고 싶은 경우를 생각해보자
  • 의미없는 수는 절대 최소가 될 수 없다.

  • 예를 들어 5455-+-+ ++과 같은 것들.

  • 최소를 구하기 위해서는 의미 없는 것을 하지 않고 중복되는 것을 하지 않으면 된다
  • 숫자와 +,- 버튼이 있는데, 반드시 숫자 버튼을 먼저 누르고, +,-를 어떻게 눌러야 할지 결정해줘야 한다.
  • 섞어 누르면 절대 최소가 될 수 없다-> 여기서 알 수 있는 것은 +나 - 중에서 어떤 것을 누를지 결정한 이후에 그것만 눌러야 한다.

  • 숫자버튼을 누르지 않는 경우, +,-를 누르지 않는 경우도 고려해야한다.

  • 이동하려는 채널 N은 (0<=N<=500000)
  • 이동하려고 하는 채널을 C라고 했다면, C의 범위는 0부터 50만까지면 될까 ?
  • 아니다. 50만을 이동해야하는데, 1과 5만 누를 수 있는 경우,
  • 채널은 무한대 만큼 있다고 했다.
  • 50만을 이동해야하는데, 1과 5만 이동만 누를 수 있다면
  • 155,555 -> 5 00,000보다
  • 511,111-> 500,000이 더 좋다. (연산 횟수가 작기 때문에)
  • 따라서 50만이 넘는 것도 정답이 될 수 있다.
  • 그러므로 C의 범위를 0<=C<=1,000,000으로 해봤다. 이 말은 맞는 말이다.
  • 제일 처음에 0을 보고있다고 하면
  • 0에서 50만까지 숫자버튼을 누르지 않고 이동한다면 +를 50만번 눌러야 한다.

  • 이 경우가 모든 숫자 버튼이 고장나 있고, 이 때 +나 -만 이용해서 구할 수 있는 답중 최대가 나온다.

  • 정답이 가장 클 때는 숫자 버튼으 없을 때 일 것이다.
  • 앞에서 100만이 나온 경우는, 이 반대로 정답이 큰 곳에서 작아지는 경우, 가장 큰 거는 100만 정도이기 때문이다.

  • 100만까지 이동해도 정답이 될 수도 있다는 가정을 할 수 있게 된다.

  • +와 -는 번갈아 누르면 안된다. +나 -는 채널을 증가시키거나 감소시키거나 둘 중 하나다.
  • 내가 보고 있는 채널보다 이동하려는 채널이 크면 +, 더 작으면 -. 눌러야 하는 횟수는 두 채널의 차이만큼이다.

문제 풀이 전략

  1. 이동할 채널 C를 정한다
for (int i= 0; i <= 1000000; i++){
    int c = i;
}

  1. C에 포함되어 있는 숫자 중에 고장난 버튼이 있는지 확인한다

    • 수를 문자열로 바꾼 다음, 한 글자씩 검사하는 방법
    • 수를 10으로 계속해서 나누면서 하나식 검사하는 방법
    • (시간복잡도가 수의 길이만큼 걸려서 구현하기 편한 쪽이 더 좋다)
  2. 고장난 버튼이 포함되어 있지 않다면 C-N 을 계산해 +나 -버튼을 몇 번 눌러야 하는지를 계산한다. 
bool broken[10];
bool possible(int c){
    while (c>0){
        if (broken[c%10])
            return false
        c /=10;
    }
    return true;
}
  • 버그가 하나 있다. c의 값이 특정한 값이면 항상 True를 리턴. 바로 C가 0일 때.
  • 가능한 C의 범위는 0<=C<= 100만
if (c == 0){
    if (broken[0]){
        return false;
    }else{
        return true;
    }
}
  • 나누기를 한 횟수는 결국 수자 몇 자리 수인지 구하는 것과 일치.
  • possible을 불가능하면 0, 가능하면 버튼을 눌러야 하는 횟수를 리턴하게 변경
int possible(int c){
    if (c == 0){
        return broken[0] > 0 : 1;
    }
    int len = 0;
    while (c > 0){
        if (broken[c%10]) return 0;
        len += 1;
        c /= 10;
    }
    return len;
}
  • 숫자버튼을 누르지 않는 경우도 있을 수 있다고 했다.
  • 100번을 제일 처음 보고 있다.
  • 100번에서 +나 -만 이용해서 채널을 이동해야한다.
  • 제일 처음에 정답을 N-100 설정하게 되면, 몇번 만에 이동해야하는지를 먼저 구할 수 있다.
  • 숫자 버튼을 누르지 않고 이동하는 횟수는 지정되어있다.

코드

n = int(input())
m = int(input())
broken = [False] * 10
if m > 0:
    a = list(map(int, input().split()))
else:
    a = []
for x in a:
    broken[x] = True

# 문자열을 이용하여 한 자리수로 만들기
def possible2(c):
    if c == 0:
        return 0 if broken[0] else 1
    c_list = list(map(int, list(str(c))))
    for i in c_list:
        if broken[i]:
            return 0
    return len(c_list)

# //와 % 이용하여 한 자리수로 만들기
def possible(c):
    if c == 0:
        if broken[0]:
            return 0
        else:
            return 1
    l = 0
    while c > 0:
        if broken[c % 10]:
            return 0
        l += 1
        c //= 10
    return l


ans = abs(n-100)
for i in range(0, 1000000+1):
    c = i
    l = possible(c)
    if l > 0:
        press = abs(c-n)
        if ans > l + press:
            ans = l + press
print(ans)

참고자료 codeplus

0%