백준 1107(리모컨) 파이썬(python3) 해결

 

문제 링크

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

1107번: 리모컨

 

 

문제의 내용을 바탕으로 풀이를 정리했습니다

 

주어진 기본 내용

 

1. 이동 허용한 채널의 범위는 0 ~ 500,000

2. 현재 접속 중인 채널 번호 = 100

 

 

★ 채널 이동은 0 미만 ( -1 ~)은 불가, 500,000 이후 (500,001 ~)는 가능.

   -> 문제에서 "0에서 -를 누르면 변화 없음, 채널은 무한대만큼 있다."라고 언급했습니다.

 

---

 

조건으로 "고장 난 버튼"이 존재합니다.

채널 이동 시 번호 입력에 제한을 주는 존재입니다. 원하는 채널로 즉시 이동 불가합니다.

 

입력 예제 7을 바탕으로 답안 예시

 

---

 

주요 예외 사항

 

1. 현재 채널이 100임을 반드시 기억합니다.

 

-> 현재 채널이 100이라서 100번으로 이동하려는 모든 테스트 케이스의 결과는 0입니다.

이동할 필요 없이 현재 채널이기 때문입니다.

 

 

-> 이동하고자 하는 채널 102이고, 고장 난 버튼이 3, 4라고 가정합니다.

이때, 직접 채널 102 입력(3) 하는 것보다 현재 채널(100)에서 +버튼 2번 누르는 것이 더 빠릅니다.

 

 

따라서 최단 입력을 구하고자 할 때는

현재 채널(100)에서 +,- 만 사용해 이동한 횟수를 비교 대상에 두어야 합니다.

 

 

2. 이동하고자 하는 채널이 0 ~ 500,000이라고 500,000 이상의 채널을 갈 수 없진 않습니다.

 

 

 

위의 이미지처럼, 500000채널을 가고자 하는데 0, 4, 5, 9 버튼이 고장 났습니다.

 

 

500000 이하의 채널에서 최대한 가깝게 번호를 구성할 수 있는 것은 "388888"입니다.

이 때 버튼 입력 횟수는 111118입니다.

 

 

그런데, 문제에서 채널의 번호는 무한대라고 언급했습니다.

500000을 넘는 채널도 존재한다는 의미입니다.

그래서 "611111"채널 입력 후 -버튼으로 111111번 이동하는 것이 111117로 더 빠릅니다.

 

---

 

 

각각의 경우에 대한 출력 방법을 구상해서 코드로 만들어 보았습니다.

[전체 코드는 가장 아래에 배치했습니다.]

적용된 경우는 다음과 같습니다.

 

1. 이동하고 싶은 채널이 100 (채널 이동이 필요 없을 때)

 

 

 

이는 함수로 만들었습니다.

sys.exit(0) 메서드는 "import sys"해서 사용할 수 있습니다. 즉시 종료 이벤트입니다.

 

 

---

 

2. 고장 난 번호가 없는 경우

 

 

고장 난 번호가 1개도 없다는 것은 직접 채널 번호를 입력할 수 있다는 것입니다.

 

 

★[주요 예외 사항] 1번의 두 번째 항목을 유의하시기 바랍니다.

이동하고 싶은 채널은 102입니다. 직접 입력하면 3번 (102)입니다.

하지만, + 버튼으로 2번(++)만에 102에 도달할 수 있습니다.

 

 

그래서 현재 채널에서 +.- 만으로 이동한 횟수와 직접 채널 번호를 입력한 횟수를 비교합니다.

관련 코드 캡처입니다.

 

 

---

 

3. 모든 번호가 고장 난 경우

 

 

 

번호 전부가 고장 나면 원하는 채널까지 +,-만 사용합니다.

 

 

---

4. 일반적인 경우 (일부의 버튼이 고장 났고, 채널 이동이 필요할 때)

 

여기서 다시 고려할 부분은 버튼이 고장 났지만, 채널 번호와 연관이 없는 경우입니다.

2번 경우와 동일한 처리 방식입니다.

하지만, 문제에서 요구하는 입력방식 때문에 이곳에서 다시 분기합니다.

 

 

 

 

 

최단 횟수를 찾기 위한 과정은 아래와 같습니다.

 

 

 

여기서 적용된 방식이 전수조사(Brute Force)입니다.

가능한 모든 경우를 하나씩 확인해서 결과를 도출하는 방법입니다.

 

 

 

---

최종 입력 코드

 

import sys # 입력 처리용
main_ch = 100  # 현재 채널
ch = input() # 이동할 채널
cnt = int(input()) # 고장난 버튼 개수

Move_ch = abs(100 - int(''.join(map(str, ch)))) # 채널 이동 횟수

def IsCh100(ch): # 채널이 100인지 확인
    if ch == '100':
        print(0)
        sys.exit(0) # 종료

'''고장난 버튼이 없어서 입력이 0일 때'''
if cnt == 0:
    #-> 그냥 채널 입력, 100채널과 근접하면 +-이동
    IsCh100(ch)
    if Move_ch < len(ch):
        print(Move_ch)
        sys.exit(0)
    else:
        print(len(ch))
        sys.exit(0)

# 고장난 버튼 집합
nButton = set(sys.stdin.readline().split())

if cnt == 10: # 모든 버튼이 고장
    # -> +-로만 채널 이동
    IsCh100(ch)
    print(Move_ch)
    sys.exit(0)

'''입력한 채널이 100이면 즉시 종결'''
IsCh100(ch)

'''여기부터 일반적인 처리 과정 기록'''
Low_num = -1  # 가능한 작은 채널
High_num = 500001 # 가능한 최대 채널
Ch_num = int(''.join(map(str,ch))) # 이동할 채널 정수화

# 입력 채널 번호에 해당하는 버튼이 정상일 때
if len(set(ch) & nButton)== 0: 
    print(min(Move_ch, len(ch)))
    sys.exit(0)
    
'''이동할 채널보다 작은 번호에서 입력 횟수 구하기'''
ableN = Ch_num-1
while ableN > -1 :
    if len(set(str(ableN)) & nButton) > 0:
        ableN -= 1
    else:
        Low_num = len(str(ableN)) + (Ch_num - ableN)
        break
        
'''이동할 채널보다 큰 번호에서 입력 횟수 구하기'''
ableN = Ch_num+1
while ableN < 1000000:
    if len(set(str(ableN)) & nButton) > 0:
        ableN += 1
    else:
        High_num = len(str(ableN)) + (ableN - Ch_num)
        break


'''작은 번호에서 경우를 찾지 못했다면(-1) 비교 대상에서 제외함'''
if Low_num == -1:
    print(min(Move_ch, High_num))
else:
    print(min(Move_ch, High_num, Low_num))

 

참고에 도움이 되었길 바랍니다.

읽어주셔서 감사합니다.

 

 

-끝-