[알고리즘][Python] 백준 12852 1로 만들기 2 문제 풀이

문제 출처 : www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

---

문제 해석 : 나누기 3, 나누기 2, 빼기 1을 수행해서 1로 만드는데 가장 적은 횟수의 연산을 한 경우를 찾는 것이다.

 

문제 풀이 : Q를 이용하면 풀 수 있다.

---

풀이 코드

from collections import deque

N = int(input())
Q = deque()
Q.append([N])
answer = []

while Q:
    arr = Q.popleft()

    x = arr[0]
    if x == 1:
        answer = arr
        break

    if x % 3 == 0:
        Q.append([x//3] + arr)

    if x % 2 == 0:
        Q.append([x//2]+arr)

    Q.append([x-1]+arr)

print(len(answer)-1)
for i in range(len(answer)-1, -1, -1):
    print(answer[i], end = " ")

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.