1로 만들기

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

내가 쓴 코드

BFS를 사용하여 풀었다.

from collections import deque


n = int(input())


def bfs(x):
    q = deque([x])
    visited = [-1] * (x + 1)
    visited[x] = 0

    while q:
        x = q.popleft()

        if x == 1:
            return visited[x]

        if x % 3 == 0 and visited[x // 3] == -1:
            q.append(x // 3)
            visited[x // 3] = visited[x] + 1
        if x % 2 == 0 and visited[x // 2] == -1:
            q.append(x // 2)
            visited[x // 2] = visited[x] + 1
        if visited[x - 1] == -1:
            q.append(x - 1)
            visited[x - 1] = visited[x] + 1


print(bfs(n))

다이나믹 프로그래밍을 이용한 코드

문제를 풀고나니 다이나믹 프로그래밍으로 분류되어 있길래 다이나믹 프로그래밍을 이용해서 다시 풀어봤다.

BFS로 구할 때는 n부터 계산했는데, DP로 구할 때는 1부터 계산했다.

채점 결과, 위의 BFS를 이용한 코드가 아래 DP를 이용한 코드보다 더 빠르다.
DP를 이용한 코드는 모든 경우를 비교하며 계산해서 더 오래 걸리는 것 같다.

n = int(input())

dp = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])