1463번: 1로 만들기

from collections import deque

x = int(input())
arr = {}
queue = deque([[x,1]])
count = 0
while queue :
    t,count = queue.popleft()
    if t < 1 : continue
    if t == 1 : break
    if t not in arr :
        arr[t] = 1 
        if t % 3 == 0 :
            queue.append([t // 3, count+1])
        if t % 2 == 0 :
            queue.append([t // 2, count+1])
        queue.append([t - 1, count+1])

print(count-1)

• 문제정리

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

  다음 세가지 연산을 조합해서 정수 N을 1로 만드는 최소의 연산 최솟값을 출력하시오

• 풀이과정

  매우 짧은 시간 제한으로 인하여 dp로 풀어야겠다고 생각하였다.

  간단하게 3개의 연산을 사용하되 이미 지나간 숫자는 다른 숫자에서 탐색하고 있을 것이니 더이상 탐색을 하지 않도록 큐에 넣지 않았다.

  이 반복을 끝날때까지 진행하여 풀이하였다.

• 풀이 후

  다른사람풀이를 보니 비슷하나 큐를 사용하지 않고 배열을 사용하여 순회하였는데

  for i in range(2,n+1): 을 반복하였는데 어차피 최대한 반복해봤다 -1씩 계속하게 됨으로 n+1번만 반복하게 된다는 점을 이용한 것 같았다.

  괜찮은 접근인것 같다.