[백준] [Python] 1463번 1로 만들기 - DP

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

1463번: 1로 만들기

 

 

Python

1. Dynamic Programming

import sys

n = int(sys.stdin.readline().rstrip())

d = [0]*1000001
d[1] = 0

# 1로 만들어야 하니깐 발상의 전환으로
# 1부터 n까지 가는데 필요한 연산 수 누적하기
# 곱셉 없이 n보다 작은 수밖에 없으므로 for문으로 가능
for i in range(2, n+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)
    d[i] = d[i-1]+1
    
print(d[n])
# print(d[:n+1])

 

 

2. BFS (큐) -- 시간초과

import sys

d = [0]*1000001

def bfs(k):
    global cnt,d
    if k==1:
        return

    x = k//3 if k%3==0 else -1
    y = k//2 if k%2==0 else -1
    z = k-1 if k-1>=0 else -1

    for op in [x,y,z]:
        if op == -1:
            continue
        #print(op,k)
        d[op] = d[k]+1 if d[op] == 0 else min(d[op], d[k]+1)
        bfs(op)

    

bfs(int(sys.stdin.readline().rstrip()))
print(d[1])