[Algorithm] 1로 만들기

이코테 p.217

피보나치 수열같은 느낌의 대표적인 dp 기본 문제다. 나는 bfs 가 먼저 떠올라서 bfs 로 풀었다.

 

BFS 풀이

from collections import deque

def bfs(n):
    q = deque()
    q.append((n, 0))
    while q:
        x, cnt = q.popleft()
        if x == 1:
            print(cnt)
            exit()
        if x % 5 == 0 and x / 5 > 0 and not visit[x // 5]:
            newX = x / 5
            visit[newX] = True
            q.append((newX, cnt + 1))
        if x % 3 == 0 and x / 3 > 0 and not visit[x // 3]:
            newX = x / 3
            visit[newX] = True
            q.append((newX, cnt + 1))
        if x % 2 == 0 and x / 2 > 0 and not visit[x // 2]:
            newX = x / 2
            visit[newX] = True
            q.append((newX, cnt + 1))
        if x - 1 > 0 and not visit[x - 1]:
            newX = x - 1
            visit[newX] = True
            q.append((newX, cnt + 1))


n = int(input())
visit = [False] * 30001
bfs(n)

 

 

DP 풀이

Bottom-up 방식으로 품

f(2)와 같은 함수들이 여러 번 호출되는 것을 알 수 있으므로, 거기서 DP 써야겠다는 포인트를 알아챌 수 있는거임

x = int(input())

d = [0] * 30001

for i in range(2, x + 1):
    d[i] = d[i - 1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])