1463번 - 1로 만들기

시간제한 : 1.5초(python 3)
메모리 제한 : 128MB

---

문제

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

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

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

---

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

---

출력

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

---

예제 입력 1

2

---

예제 출력 1

1

예제 입력 2

10

---

예제 출력 2

3

---

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

---

코드

import sys
from collections import deque

X = int(sys.stdin.readline().strip())

# 횟수를 의미
L = 0
# 루트 노드인 X를 처음에 삽입
Q = deque([X])

# 1이 되었는지 확인하는 변수
flag = False

# Q가 비었을 때까지 반복하지만 1이 되면 종료함
while Q:
    # Q의 원소 수만큼 반복
    n = len(Q)
    for _ in range(n):
        # Q의 원소 하나 빼기
        v = Q.popleft()
        # 1이 됐으면 출력하고 종료
        if v == 1:
            flag = True
            print(L)
            break

        v_2, v_3 = (v%2 == 0), (v%3 == 0)
        
        # 3으로 나눠지면 Q에 v//3 삽입
        if v_3:
            Q.append(v//3)
        # 2으로 나눠지면 Q에 v//2 삽입
        if v_2:
            Q.append(v//2)
        # v-1도 Q에 삽입
        Q.append(v-1)
    if flag:
        break
    
    # 횟수 1회 추가
    L += 1

---

풀이

시간 : 87856ms
메모리 : 1140KB

이 문제의 경우 최소 횟수를 구하는 문제이므로 BFS를 이용해 풀이해보았다.

먼저 X를 루트로 생각하고 연산 세 가지를 진행한 자식노드 3개를 만들어 Q에 넣는다.
이때 만약 2나 3으로 나누어 떨어지지 않는 경우 그 연산은 진행하지 않는다.
그렇게 자식노드 3개를 Q에 넣었다면 그 자식노드를 기준으로 위와 같이 연산 세 가지를 진행한 자식노드 3개를 만들어 Q에 넣는다.
이렇게 진행하다가 1이 되었다면 flag를 True로 만들어 연산 횟수(L)를 출력한다.