[23-24 동계 모각코] 1회차 결과

백준 1107 - 리모컨

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

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

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

 

문제링크 - https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

문제 해결을 위해 고려한 조건 + 구현 방식

 

1. 목표 채널은 50만 채널 이하이지만, 채널수는 무한대

-  50만 보다 큰 채널에서, 목표채널로 이동할 가능성이 있다. (50만 채널까지만 탐색하면 안됨)

 

2. 고장난 버튼이 없는 경우, 입력받지 않음

- 런타임 에러가 발생할 수 있으므로, 고장난 버튼 개수가 0 일때, 입력받지 않도록 처리해야한다.

broken = [] if M == 0 else list(map(int, sys.stdin.readline().split()))  # 고장난 버튼

 

3. 고장난 버튼을 포함하지 않는 채널들만 탐색

- 입력 받은 고장난 숫자버튼 들을 포함하지 않는, 채널들만 고려하여 최소 버튼 조작횟수를 계산해야 한다.

 

4. 현재 채널, 최소 버튼 조작 횟수 초기값 설정

- 처음 채널이 100이기 때문에, 목표 채널이 100인 경우, 최소 버튼 조작 횟수도 숫자 버튼을 눌러 100채널로 이동할 필요 없이, |목표채널 - 현재채널| → |100 - 100| = 0 으로 초기값을 설정해야한다.

cur = 100  # 현재 채널
min_sub = abs(N - cur)  # 최소 버튼 조작 횟수 (초기값)

 

5. 숫자 버튼을 눌러, 특정 채널로 이동는 경우

- 현재 채널을 특정 채널로 갱신하고, 현재 채널에서 목표 채널의 차이와, 특정 채널로 이동 할 때  누르는 숫자 버튼 수를 더하여 현재 최소로 누르는 버튼 수 와 비교하여 최소값을 갱신해야한다.

 

 

문제 리뷰

처음 문제를 파악했을 때, 가장 기본적인 접근방법으로 가능한 모든 경우의 수를 탐색하는 알고리즘인 '브루트 포스(brute force)' 를 사용하여 문제를 해결해야겠다고 생각했다. 

 

브루트 포스 (brute force)

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 장점은 예외가 없이 모든 경우의 수를 파악할 수 있다는 점이고, 반대로 단점은 그만큼 시간 복잡도가 늘어날 수 있다. 

 

 

코드 설명

def check(num, broken):
    num = str(num)
    for i in num:
        if int(i) in broken:
            return False
    return True

 

선택된 숫자가 고장난 버튼이면 False 아니면 True를 반환하는 check 함수를 구현하여 이용했다.

 

# 100만 채널까지 탐색 (채널은 무한대 까지 있다. 하지만, 50만 까지만 입력받는다.)
    for i in range(1000001):
        # i가 고장난 버튼을 포함하지 않는다면
        if check(i, broken):
            min_sub = min(min_sub, len(str(i)) + abs(N - i))  # 최소값 갱신

 

100만 보다 큰 채널 까지 탐색 하지 않는 이유는 목표채널로 50만 채널까지 입력 받기 때문에, 100만 초과 채널에서 목표 채널로 가기위해 (-) 버튼을 누르는 횟수가 50만 채널 이하에서 목표채널로 가기 위해 (+) 버튼을 누르는 횟수 보다 항상 크기 때문이다. (100만 초과 채널은 7자리 숫자기 때문에, 처음 채널 이동할 때 누르는 버튼 수도 7개로 50만 이하 채널 6개보다 많다.)

 

또한, 최소값을 갱신할 때 현재 최소값과, 특정채널이동을 위해 누르는 숫자 버튼 수 + 특정채널에서 목표채널의 차이를 비교하여 갱신했다.

 

 

 

전체 코드

import sys

# 선택된 숫자가 고장난 버튼을 포함하는지 확인
def check(num, broken):
    num = str(num)
    for i in num:
        if int(i) in broken:
            return False
    return True


def main():
    N = int(sys.stdin.readline().rstrip())  # 채널 번호
    M = int(sys.stdin.readline().rstrip())  # 고장난 버튼 개수
    broken = [] if M == 0 else list(map(int, sys.stdin.readline().split()))  # 고장난 버튼

    cur = 100  # 현재 채널
    min_sub = abs(N - cur)  # 최소 버튼 조작 횟수 (초기값)

    # 100만 채널까지 탐색 (채널은 무한대 까지 있다. 하지만, 50만 까지만 입력받는다.)
    for i in range(1000001):
        # i가 고장난 버튼을 포함하지 않는다면
        if check(i, broken):
            min_sub = min(min_sub, len(str(i)) + abs(N - i))  # 최소값 갱신

    print(min_sub)


if __name__ == "__main__":
    main()

 

---

# 다행히 시간안에 문제를 해결 할 수 있었다. 여러가지 조건들을 고려하면서 문제푸는데 적용하는 훈련을 하게 되었고, 브루트 포스 알고리즘에 대해 조금 더 공부하는 시간이 되었다.