• 링크 : https://www.acmicpc.net/problem/1107
  
  
  

• 못풀었음 - 나중에 다시 풀자
  - 정답 및 해설 코드1 : https://hae-sooo97.tistory.com/44
  - 정답 및 해설 코드2 : https://jennnn.tistory.com/60

[나의 경우]

• 고장난 버튼 정제해서 올바른 버튼으로 permutations 수행
  • 모든 경우의 수를 다 보려 했으나 어디서 계산실수인지 뭔지 한듯

[정답 경우]

• 일단 고장난 버튼 정제할 필요 없었음
• 버튼 클릭의 경우, 순열 말고 { for nums in range(1000001): }를 수행하면 되는거였음
  • 이게 브루트포스 문제다!
• for문으로 버튼 클릭한 숫자를 100만까지 만드는데,
  • 블로그 보면 알겠지만 +버튼 1~50만까지랑, -버튼 100만~50만임
• (핵심) 수식을 세워야하는데
  • 테스트케이스 보고 세운듯...
  • 그리고 초기 min값도 테케보고...

---

---

나의 뜨레기 코드 - 메모용

1차 작성

메모

• 숫자 버튼은 0~9

• 버튼은 + -

• 채널 0 ~ 무한대 (0에서 -하면 0)

• 현재 채널은 100, 이동할 채널은 n -> 최소 몇 번 눌러?

  • 숫자를 입력해서 += 1해도 되고
  • +- 눌러서 += 1 해도 됨

• 고장난 버튼이 m개 주어짐

  • 고장난 버튼 누르면 continu인듯

아이디어

• 일단 디폴트로 수행해둘것

  • n = 100인 경우
    • 무조건 0 출력 후 return이 아니었네, 예제 2번 봐
  • 시작할 때, ans = len(n)
    • 기본적으로 이동할 n의 숫자 입력하면 채널 이동됨
    • 이후 min(a, b)하면서 진행하면 될듯

• 프로세스 어케하냐

  • 이것도 순열과 조합으로 할 수 있나? (permutation으로 모든 경우의 수 해야할듯)
  • not_button = [고장난 버튼]
  • button = [{0~9} - {not_remote} + {x+1, x-1}]
  • for i in range(len(button)):
    • for remote in permutations(button, i): # -> 모든 경우의 수
      • if remote == n: min(ans, len(remote)) 이렇게?

시간복잡도

변수

• min값 저장할 ans
• 고장난 버튼 리스트와 고장안난 버튼 리스트(이때, +랑- 어케할지..)
• permutations 가능한지 확인하기

---

# 2차 작성
from itertools import permutations

n = str(5457)
#n = str(10)
not_button = [6,7,8]
button = [i for i in range(10)]

for i in not_button:
    if i in button:
        button.pop(button.index(i))
ans = []
nn_list = []

for j in range(1, len(button)):
        
    for remote in permutations(button, j):
        if remote[0] == 0:            continue   # 0으로 시작하는 경우는 패스
        # 모든 경우의 수로 찾기 가능한 경우
        tmp = "".join(map(str,list(remote)))
        if tmp == n:
            ans.append(len(tmp))
            break
        else:
            nn_list.append(tmp)
            
# 모든 경우의 수에 포함 안되었을 때, + - 로 찾는 경우
for candi in nn_list:
    tmp_plus = len(candi)
    while int(candi) < int(n):
        candi = str(int(candi) + 1)    # "+" 버튼
        tmp_plus = tmp_plus + 1              # + 누른 횟수 추가

        if candi == n:
            #print(tmp, " ", tmp_plus-1)
            ans.append(tmp_plus)
            break
#print(ans)
print(min(ans))