-
[Python 3] BOJ - 1107 "리모컨"BOJ 2020. 4. 17. 21:03
# 문제 풀이 : https://www.acmicpc.net/problem/1107
# 풀이 :
개인적으로 이 문제의 핵심은 가능한 경우를 나누는 것과 경계값 예외 처리라고 생각한다. 리모컨의 고장 여부에 따라, 특히 어떤 수가 고장났느냐에 따라 임의의 채널에 갈 수 있는지 없는지가 바뀐다. 따라서 최악의 경우는 +-만 쓸 수 있는 경우이고 최선의 경우는 하나도 고장나지 않는 경우이다. 평균적인 경우는 n개가 고장나서 +-와 10 - n개만 쓸 수 있는 경우이다. 최선의 경우는 평균적인 경우에서 n이 0인 경우이고 평균적인 경우안에 최악의 경우가 포함되어 있으므로 평균적인 경우만 계산하면 된다
위의 그림 1에서 최악의 경우는 abs(X - 100)이다. 평균적인 경우는 최악의 경우를 포함하므로 두 경우가 같아지게 하는 수를 Y까지 조사하면 최소로 리모컨을 누르는 경우를 구할 수 있다. 그러나, 이는 Y에 도달할 수 있음을 전제로 하고 있다. 도달하지 못하는 경우는 도달하는 경우보다 누르는 횟수가 클 수 밖에 없다. 왜냐하면 자릿수는 1차이 나지만, 절댓값의 차이는 1보다 크거나 같기 때문이다. 따라서, 도달하지 못하는 경우도 최악의 경우와 같다고 할 수 있다. 만일 X가 100보다 작은 수면 대칭으로 하고 생각하면 된다.
이를 문제 입력의 최대값인 500,000인 경우일 때 Y는 999,906이다. 입력의 최소값은 경우 Y는 존재하지 않으므로 Y는 0이다. 따라서 임의의 X에 대해 0이상 999,906이하의 경우를 탐색하면 정답을 구할 수 있다.
# 코드
import sys # target : 타켓 넘버 # n : 고장난 버튼의 갯수 # broke : 고장난 버튼 # check[i] : i번 버튼이 고장났는 지 여부 target = int(sys.stdin.readline()) n = int(sys.stdin.readline()) broke = list(map(int, sys.stdin.readline().split())) check = [True] * 10 ans = 9876543210 # 고장난 버튼 반영 for i in broke: check[i] = False # can_make : a를 현재 남아있는 버튼으로 갈 수 있는지 없는지 리턴하는 함수 def can_make(a): for k in str(a): if check[int(k)] == False: return False return True # 문제의 최소값은 0부터 최대값 999,906(1,000,000으로 대체)에 반드시 있으므로 탐색 for i in range(1000001): # 만일 해당 수에 도달할 수 있으면(평균적 경우) if can_make(i): # 최소값 갱신 ans = min(ans, len(str(i)) + abs(i - target)) # 최악의 경우(애초에 10개 모두 고장나거나, 도달할 수 없다면)는 항상 100과의 비교가 유일하므로 최소값 갱신 ans = min(ans, abs(100 - target)) # 정답 출력 print(ans)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1238 "파티" (0) 2020.04.19 [Python 3] BOJ - 1208 "부분수열의 합 2" (0) 2020.04.18 [Python 3] BOJ - 18117 "분수" (0) 2020.04.16 [Python 3] BOJ - 1080 "행렬" (0) 2020.04.14 [Python 3] BOJ - 1074 "Z" (0) 2020.04.14