백준 12852 1로 만들기 2 파이썬(python)

문제

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

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

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

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

---

풀이

[알고리즘]

BFS와 방문 체크를 이용하면 풀 수 있다. 연산 횟수의 최솟값을 구해달라 했기 때문에 BFS를 이용하고 이미 지나간 숫자를 다시 Queue에 넣는 것은 시간 낭비이기 때문에 방문 체크를 통해 패스해 준다.

 

[풀이 방법]

1. 큐에 N을 넣고 문제에서 주어진 조건대로 if문을 달아서 비교해 준다.
2. 큐에 넣기 전에 check 배열을 통해 이미 지나간 숫자인지 판별해 준다.
3. n이 1이 될 때까지 반복, 가장 먼저 1이 되는 값이 최소 연산 횟수이고 과정을 더해온 s 변수가 답이 된다.

import sys
from collections import deque

N = int(sys.stdin.readline())
q = deque([(N, 0, str(N))])
check = [False] * (N+1)

while q:
    n, t, s = q.popleft()
    check[n] = True

    if n == 1:
        print(t)
        print(s)
        break

    if not n % 3 and not check[n // 3]:
        q.append((n // 3, t + 1, s + " " + str(n // 3)))

    if not n % 2 and not check[n // 2]:
        q.append((n // 2, t + 1, s + " " + str(n // 2)))

    if not check[n - 1]:
        q.append((n - 1, t + 1, s + " " + str(n - 1)))

출처 : https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2