[백준]1463 1로 만들기 파이썬 python

문제링크

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

1463번: 1로 만들기

코드

import sys
from collections import deque
#DP접근
n= int(input())
d = [0]*(n+1)
d[1] = 0 #초항 명시
for i in range(2,n+1):
    d[i] = d[i-1]+1
    if i%2==0 and d[i]>d[i//2]+1:
        d[i] = d[i//2]+1
    if i%3==0 and d[i]>d[i//3]+1:
        d[i] = d[i//3]+1
print(d[n])
'''
#BFS 접근
input = sys.stdin.readline
x = int(input())
visited = [-1]*(x+1)
dq = deque()
dq.append(1)
visited[1]=0
while dq:
    cur = dq.popleft()
    if cur ==x:
        print(visited[cur])
        break
    for nx in[cur+1, cur*2, cur*3]:
        if nx<=x and visited[nx]==-1:
            visited[nx] = visited[cur]+1
            dq.append(nx)
'''
 

 

Point

- DP 로 접근하기

(DP의 Top-Down재귀 방식으로는 파이썬에서 메모리 초과 발생--> 대신, BottomUp반복문 사용)

1) 점화식 정의:

d(n) : n을 1로 만드는데 필요한 연산 횟수

2) 작은 문제로 쪼개기 <작게 만드는 모든 방법을 고려했는가.>

d(n) = min( d(n/3) +1, d(n/2) +1 , d(n-1) +1 )

 

- BFS로 접근하기

노드 : 숫자

간선 : 3가지 action(+1, *2, *3)