[백준 27440번] 파이썬 - 1로 만들기 3

백준 27440 - 1로 만들기 3

시간 제한 0.5초(추가 시간 없음), 메모리 제한 1024MB

# 조건

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

# 접근 방법

• 기존의 1로 만들기 문제들과 같이 dp를 활용해주면 된다.
• 다만, 숫자의 범위가 상당히 크므로 모든 숫자를 반복하여 체크한다면 시간초과가 발생한다.
• 따라서, 방문 배열이 아닌 방문 딕셔너리를 활용하여, 이 숫자가 이전에 방문한 적이 있는지 체크해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

N = int(input())  
q = deque()  
q.append(N-1)  
visited = dict()  
visited[N] = 0  
visited[N-1] = 1  
if not N % 2:  
    q.append(N//2)  
    visited[N//2] = 1  
if not N % 3:  
    q.append(N//3)  
    visited[N//3] = 1  

while not 1 in visited:  
    val = q.popleft()  

    if not val - 1 in visited:  
        visited[val-1] = visited[val] + 1  
        q.append(val-1)  

    if not val % 2 and not val // 2 in visited:  
        visited[val//2] = visited[val] + 1  
        q.append(val//2)  

    if not val % 3 and not val // 3 in visited:  
        visited[val//3] = visited[val] + 1  
        q.append(val//3)  


print(visited[1])