[Cos Pro 1급, Python] 5차 9번 : 몇번 연산을 해야 하나요

문제

정수 number와 target이 주어졌을 때, 다음 세 연산을 이용해 number를 target으로 만들려 합니다.

 

연산 1. 1을 더합니다.
연산 2. 1을 뺍니다.
연산 3. 2를 곱합니다.

 

정수 number와 target이 매개변수로 주어질 때, number로 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 하도록 solution 함수를 작성해 주세요.

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

def solution(number, target):
	answer = 0
	dp = [-1]*(2*target+1)
	for i in range(1, number+1):
		dp[i] = number - i
		dp[i*2] = dp[i] + 1
	dp[number+1] = 1
	for i in range(number + 2, target+1):
		min_num = min(dp[i-1]+1, dp[i//2]+1) if (i % 2 == 0) and (i//2 >= number) else dp[i - 1] + 1
		if dp[i + 1] != -1:
			min_num = min(min_num, dp[i + 1]+1)
		if dp[i] != -1:
			min_num = min(min_num, dp[i])
		dp[i] = min_num
		dp[i*2] = min_num + 1
	answer = dp[target]
	return answer
    
    
    
    
    
    
number1 = 5
target1 = 9
ret1 = solution(number1, target1)

print("solution 함수의 반환 값은", ret1, "입니다.")

number2 = 3
target2 = 11
ret2 = solution(number2, target2)

print("solution 함수의 반환 값은", ret2, "입니다.")