[백준] 1463번: 1로 만들기 (python)

https://www.acmicpc.net/problem/1463

---

처음에는 아무 생각 없이 BFS로 풀었다가 시간 초과로 틀린 문제

입력이 10의 6승으로 매우 크기 때문에 DP를 이용해 시간 생각을 하면서 풀었어야 했다

무작정 풀지말고 생각 먼저 하고 풀기

---

# BFS로 풀어서 시간 초과된 코드
from collections import deque

n = int(input())
q = deque()
q.append((n, 0))
ans = -1
while q:
    now, times = q.popleft()
    if now == 1:
        ans = times
        break
    if now % 3 == 0:
        q.append((now // 3, times + 1))
    if now % 2 == 0:
        q.append((now // 2, times + 1))
    q.append((now - 1, times + 1))
print(ans)

 

# DP로 풀이
n = int(input())
dp = [0] * (n + 1)

# 2부터 거꾸로 1을 만들 수 있는 연산 최솟값을 구해 나감
for i in range(2, n + 1):
	# 1을 빼는 연산을 사용하는 경우
    dp[i] = dp[i - 1] + 1
    
    if i % 3 == 0:
    	# 만약 3으로 나눠지는 경우 1을 빼는 연산과 3을 나누는 연산 중 최솟값으로 업데이트
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:
    	# 만약 2로 나눠지는 경우 1을 빼는 연산과 2를 나누는 연산 중 최솟값으로 업데이트
        dp[i] = min(dp[i], dp[i // 2] + 1)
        
print(dp[n])