[알고리즘] 백준 12852 파이썬 - 1로 만들기 2

 

12852번: 1로 만들기 2

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

문제풀이

import sys
from collections import deque
input = sys.stdin.readline
n=int(input())
#01
q=deque([[n]])
ans=[]
while q:
	#02
    x=q.popleft()
    y=x[0]
    if y==1:
        ans=x
        break
    #03
    if y%3==0:
        q.append([y//3]+x)
    if y%2==0:
        q.append([y//2]+x)
    q.append([y-1]+x)
#04
print(len(ans)-1)
print(*ans[::-1])

- #01 : q에는 초기값을 [n]으로 지정해주고, ans를 선언해준다.

- #02 : x에 q의 맨 왼쪽 값을 저장한다. y는 x의 첫번째값을 저장한다.

          즉 [n] 형태로 저장하여서, 리스트 안에 리스트 형태로 경우의 수를 찾을 것이다.

          최종적으로 y가 1인 경우를 찾으면 그 경우를 ans에 저장하고 while문을 끝낸다.

- #03 : y가 각각 3과 2로 나누어지면, q에 형식에 맞게 추가해준다.

           1을 빼는 경우의 수도 추가해준다. 즉 3가지 경우의 수를 모두 q에 추가하여,

           계속해서 y 값이 1이 될 때까지 경우를 찾아가는 것이다.

- #04 : while문이 끝나면 ans의 길이에서 1을 뺀 값을 출력하고,

           ans를 거꾸로 출력한다.