Enochkon's blog

문제

코드

from collections import deque

n = int(input())
q = deque()

q.append((n,0))

while len(q)!=0:
    c,count = q.pop()
    if(c<0):
        continue
    if(c==1):
        print(count+1)
        exit(0)
    if(c==0):
        print(count)
        exit(0)
    
    q.append((c-1,count+1))

    if(str(c).count("1")!=0):
        tmp = list(str(c))
        for i in range(len(tmp)):
            if(tmp[i]=='1'):
                q.append((int(str(c)[0:i]+str(c)[i+1:]),count+1))   

풀이

• 0을 만드는 최소 횟수를 구해라

1빼기 능력 두가지
1. 가지고 있는 수에서 1을 뺀다.가지고 있는 수에 있는 1을 하나 지운다.
2. 지우고 난 뒤 좌우의 수들을 순서대로 다시 합쳐 하나의 수로 만든다. 이때 맨 앞의 연속되는 0은 지워진다.

1. n을 입력 받는다
2. 입력 받은 n을 1빼기 능력을 사용한다.
   1. q에 n을 넣어주거 반복문을 돌린다.
   2. 매 시행마다 1빼기 능력 두가지를 사용해서 시행후의 값을 q에 넣어준다.
   3. 계속 반복문을 돌면서 0이하가 되면 없애고, 0이나 1이 되면 반복문을 중지하고 시행횟수를 출력해라