Algorithm
백준
Python
리모컨

문제 링크

https://www.acmicpc.net/problem/1107 (opens in a new tab)

내 풀이

이따구로 풀고 있었다. 진짜 역대급으로 자괴감이 드는 문제. 너무 복잡하게 생각하고 어떤 유형의 문제인지 조차도 파악을 못했다. 

goal = int(input())
goal_list = list(str(goal))
n = int(input())
broken_button = []
if n != 0 :
  broken_button = list(map(int, input().split()))
 
def go(start:int, end:int) :
  cnt = 0
  while start != end :
    if end - start < 0 :
      start -= 1
      cnt += 1
    elif end - start > 0 :
      start += 1
      cnt += 1
 
  return cnt
 
def find_most_close_member(num_list, target) :
  under, over = target, target
  while True :
    if under in num_list :
      rest = target - under
      return under, rest
    else :
      under -= 1
    if over in num_list :
      rest = over - target
      return over, rest
    else :
      over += 1
def main() :
  global broken_button, n, goal
  goal_length = len(goal_list)
 
  if goal == 100 :
    print(0)
    return
 
  num_list = []
  for i in range(10) :
    if i not in broken_button :
      num_list.append(i)
 
  close_member_str = ""
  if num_list :
    for i in range(goal_length) :
      close_member, rest = find_most_close_member(num_list, int(goal_list[i]))
      close_member_str += str(close_member)
      # 마지막 인덱스가 아니라면 rest를 추가
      if i + 1 <= goal_length - 1 :
        goal_list[i+1] = str(rest) + goal_list[i + 1]
 
  cnt = go(int(close_member_str), goal)
 
  print(cnt + len(close_member_str))
 
main()

정답

target = int(input())
ans = abs(100 - target) # ++ or -- 로 이동할 경우 -> 최댓값
M = int(input())
if M: # 고장난게 있을 경우만 인풋을 받음
    broken = set(input().split())
else:
    broken = set()
 
# 작은수에서 큰수로 이동할땐 500,000 까지만 보면 되지만
# 반대로 큰수에서 작은수로 내려올수도 있으므로 1,000,000 까지 봐야함
for num in range(1000001): 
    for N in str(num):
        if N in broken: # 해당 숫자가 번호를 눌러서 만들 수 없는 경우엔 스탑
            break
    else: # 번호를 눌러서 만들 수 있는 경우엔
    	# min(기존답, 번호를 누른 횟수 + 해당 번호로부터 타겟까지의 차이)
        ans = min(ans, len(str(num)) + abs(num - target))
 
print(ans)
ACM Craft단어 공부