[COS PRO 1급 #5-9] 몇 번 연산을 해야하나요

문제설명

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

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

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

매개변수 설명

두 정수 number와 target이 solution 함수의 매개변수로 주어집니다.
* number와 target은 0 이상 10,000 이하입니다.

return 값 설명

number를 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 합니다.

예시

| number |target|return |
|---|---|------|
| 5|9|2|
|3|11|3|

예시 설명

예시 #1
1. 5 x 2 = 10
2. 10 - 1 = 9
따라서 연산을 최소 2번 해야 합니다.

예시 #2
1. 3 x 2 = 6
2. 6 x 2 = 12
3. 12 - 1 = 11
따라서 연산을 최소 3번 해야 합니다.

문제 코드

def solution(number, target):
    #여기에 코드를 작성해주세요.
    answer = 0
    return answer

풀이 1

# 동적계획법: https://velog.io/@bonjaski0989/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-%EC%A0%95%EB%A6%AC%EA%B8%80Python

def solution(number, target):

	dp = [0] * (target*2+1)
	
	# 1~number까지 연산횟수 구하기
	for i in range(1, number+1):
		dp[i] = number - i
		dp[i*2] = dp[i] + 1
	
	# number ~ target까지 연산횟수 구하기
	for j in range(number+1, target+1):
		if j % 2 == 0:
			num = min(dp[j//2]+1, dp[j-1]+1)
		else:
			num = dp[j-1]+1
		if dp[j+1] != 0:
			num = min(num, dp[j+1]+1)
		if dp[j] != 0:
			num = min(num, dp[j])
		dp[j] = num
		dp[j*2] = dp[j]+1

	return dp[target]

풀이 2

import queue

def solution(number, target):
	answer = 0
	visited = [0 for _ in range(10001)]
	q = queue.Queue()
	q.put(number)
	visited[number] = 1
	while not q.empty():
		x = q.get()
		if x == target:
			break
		if x+1 <= 10000 and visited[x+1] == 0:
			visited[x+1] = visited[x]+1
			q.put(x+1)
		if x-1 >= 0 and visited[x-1] == 0:
			visited[x-1] = visited[x]+1
			q.put(x-1)
		if 2*x <= 10000 and visited[2*x] == 0:
			visited[2*x] = visited[x]+1
			q.put(2*x)
	answer = visited[target]-1
	return answer