[알고리즘][파이썬]1463-1로 만들기 (BFS/DP)

 

 

 

문제

 

 

1.BFS코드

import sys
from collections import deque

x = int(sys.stdin.readline().strip())

def fun(start_x):
    q= deque()
    q.append((0,start_x))
    while(q):
        C, cur_x =q.popleft()
        if(cur_x==1):
            return C
        elif(cur_x!=0):
            if(cur_x % 3 == 0): q.append((C+1,cur_x//3))
            if(cur_x % 2 == 0): q.append((C+1,cur_x//2))
            q.append((C+1,cur_x-1))

print(fun(x))

#큐에 연산 횟수, 연산 결괏값을 넣어 와일문을 돌려서 1이 나올 때의 연산 횟수 반환했다.

 

 

2.DP코드

x=int(input())
d=[0]*(x+1) # 1-based
for i in range(2,x+1): # 2부터 x까지 반복
    d[i]=d[i-1]+1 #1빼기
    if i%2==0: #2나누기
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: #3나누기
        d[i]=min(d[i],d[i//3]+1)
    #각 연산 중 최소가 d[i]에 저장
print(d[x])

#d[i]는 숫자 i가 1이 되기 우한 최소 연산 횟수이다.