자연수x,y,n이 매개변수로 주어질 때,x를y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때x를y로 만들 수 없다면 -1을 return 해주세요.
제한 조건
1 ≤ x≤y ≤ 1,000,000
1 ≤n<y
입출력 예
x y n result
10
40
5
2
10
40
30
1
2
5
4
-1
입출력 예 설명
입출력 예 #1 x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #2 x에n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #3 x를y로 변환할 수 없기 때문에 -1을 return합니다.
✍ 접근
처음에는 deque나 heap을 사용할 까 생각했다.
그러나 시간초과.
최대 y+1개가 있는 배열을 만들고, 기존에 주어진 숫자 x를 기준으로 *2, *3, +n을 하며 배열의 끝까지 도달할 수 있는지를 구하는 방법이 번뜩 떠올랐다!
== dp로 풀었다
정답코드
def solution(x, y, n):
dp = [2147000000]*(y+1)
dp[x] = 0
for i in range(x,y+1):
if i * 3 <= y:
dp[i*3] = min(dp[i*3],dp[i]+1)
if i * 2 <= y:
dp[i*2] = min(dp[i*2],dp[i]+1)
if i + n <= y:
dp[i+n] = min(dp[i+n],dp[i]+1)
return -1 if dp[-1] == 2147000000 else dp[-1]
해설
dp를 최대값(2147000000으로 해주었지만 1000001로 해줘도 될 것 같다)으로 y+1개의 배열을 만들어준다
시작 지점(x)는 0
x부터 y+1까지 배열을 순회하면서
list를 벗어나지 않기 위해 각각 if문을 사용해주고,
dp[i*3]혹은 dp[i*2]혹은 dp[i+n]이 진작 방문되었을 때(2147000000이 아닌 값이 들어있을 때) 그 값과 새로 들어오는 (dp[i]== 전 위치 + 1)을 비교해서 작은 값을 넣어준다
만약 dp[-1]그러니까 y까지 도달했다면 dp[-1]이 최소값일 것이고, y에 도달하지 못했다면 -1을 return하면 된다
⭐ 배움
다른 사람들의 코드를 보니 while을 이용한 코드가 많았다. 아, 이 방법도 있었구나!를 많이 느꼈다