[이코테] 다이나믹 프로그래밍_1로 만들기 (python)

문제

1) x가 5로 나누어 떨어지면, 5로 나눈다
2) x가 3으로 나누어 떨어지면, 3으로 나눈다
3) x가 2로 나누어 떨어지면, 2로 나눈가
4) x에서 1을 뺀다
위 4개 연산을 사용해서 1을 만들때, 연산 사용 최소 횟수는?

나의 풀이

1. 바텀업 다이나믹 프로그래밍(반복문 사용)

import sys
input = sys.stdin.readline
x = int(input())

# 1 ~ x까지 각각의 최단거리를 기록하기 위해서
# 인덱스가 0부터 시작이므로, 최대 가능 x의 크기 + 1까지 리스트 생성
dp = [0] * 30001

for i in range(2, x + 1):
	# dp[i] 계산 시 1을 더하는 이유는,
	# 바로 아래 단계까지 가는 거리 1을 더해주기 위해서
    
	# 1을 빼는 경우
	dp[i] = dp[i - 1] + 1
    
	"""
	2, 3, 5로 나누어 떨어질 때, 각각 나누어 준다.
	min을 하는 이유는,
	그 수로 나누어 떨어질 때 가능한 계산의 수가
	1을 빼주거나 그 수로 나누어 주는 것뿐이기 때문
	
	min 할 때 dp[i]에 + 1을 안 하는 이유는,
	앞서 dp[i] = dp[i - 1] + 1로 정의했기 때문
	"""
	if i % 2 == 0:
		dp[i] = min(dp[i], dp[i // 2] + 1)
	if i % 3 == 0:
		dp[i] = min(dp[i], dp[i // 3] + 1)
	if i % 5 == 0:
		dp[i] = min(dp[i], dp[i // 5] + 1)
        
print(dp[x])

2. 탑다운 다이나믹 프로그래밍(재귀 함수 사용)

import sys
input = sys.stdin.readline
x = int(input())

# 1 ~ x까지 각각의 최단거리를 기록하기 위해서
# 인덱스가 0부터 시작이므로, 최대 가능 x의 크기 + 1까지 리스트 생성
d = [0] * 300001

def num(x):
	# 정수 1일때는 0번 연산
    if x == 1:
        return 0
        
    # 연산 회수가 0이 아닐때, 
	# 즉 이미 계산한 적 있을 때, 그 값을 반환
    if d[x] != 0:
        return d[x]
        
	# 나누어 떨어지지 않을 때, 최솟값이 되지 않도록 높은 값 설정
    five = three = two = 99999
    
	# 각 정수로 나누어 떨어질 때, 그 정수의 연산 회수 설정
    if x % 5 == 0:
        five = num(x // 5)
    if x % 3 == 0:
        three = num(x // 3)
    if x % 2 == 0:
        two = num(x // 2)
        
	# 연산들을 비교해서 가장 적은 연산 회수를 가진 경우 + 1
	# +1을 하는 이유: 바로 아래 단계까지 가는 거리 1을 더해주기 위해서
    d[x] = min(five, three, two, num(x - 1)) + 1
    return d[x]
    
print(num(x))