[BOJ] 1463 1로 만들기

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

처음엔 시간 초과... 다음은 메모리 초과... 가 떠서 결국 도움을 받았던 문제이다. bottom-up 방식으로 풀어야 하는데, 생각은 했지만 bottom-up을 어떻게 구현해야 하지 하다가 막혀버렸다. 그렇게 어렵지는 않은 문제인데 그것보다 부족해서 못 풀었다.. 나중에 다시 풀어보자

정답코드

import sys

n = int(sys.stdin.readline())
dp = [0] * (n+1)
"""Bottom-up"""
for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    if i%2 == 0 and dp[i] > dp[i//2] + 1:
        dp[i] = dp[i//2] + 1
    if i%3 == 0 and dp[i] > dp[i//3] + 1:
        dp[i] = dp[i//3] + 1
print(dp[n])

시간 초과

def dfs(depth, result):
    global answer
    if result == 1:
        answer = min(answer, depth)
        return
    if result % 2 == 0:
        dfs(depth+1, result // 2)
    if result % 3 == 0:
        dfs(depth+1, result // 3)
    dfs(depth+1, result-1)
dfs(0, n)
print(answer)

메모리 초과

dq = deque([[n,depth]])
while dq:
    x, depth = dq.popleft()
    if x % 2 == 0:
        if x//2 == 1: break
        dq.append([x//2, depth+1])
    if x % 3 == 0:
        if x//3 == 1: break
        dq.append([x//3, depth+1])
    dq.append([x-1, depth+1])

print(depth+1)