숫자 변환하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

문제풀이

해당 문제를 해결하려면 중복된 계산을 최소화시켜야 한다. 이는 점화식으로 해결할 수 있다.

 

• float("inf")로 요소를 초기화 시켜준다. 무한대를 가지는 부동소수점 값이며 최소 값을 업데이트할 때 사용된다.
• x, y는 초기 값이 같을 수 가 있다. 따라서 dp [x]는 0으로 초기화해준다.
• 부분합이 y가 넘지 않는 한에서 각 최소 횟수를 갱신해준다.
• 해당 과정을 반복하다 보면 x와 y가 같아질 수 있을 때 dp [y] 번째는 각 계산 이후 최소 값으로 갱신하게 된다. 

1번째 테스트 케이스를 볼 때 중복되는 부분이 몇 가지 있다.

x * 3 = 30, x * 3 + n = 35... and (x + n) * 2 = 30, (x + n) * 2 + n = 35... 결과는 같지만 결과까지의 연산 횟수는 후자가 1이 더 높다. dp [k]이 무한대일 경우 min 연산시 어떤 값 이든 최소 값을 가지게 되고 이미 무한대 외에 다른 값이 존재한다면 그중의 최소 값이 할당된다. 따라서 dp [30], dp [35], dp [40]의 최소 값은 각각 1, 2, 2가 된다. 

 

3번째 테스트 케이스를 볼 때 -1이 뜨는 경우는 어떻게 처리할까?

x * 2를 제외한 어떠한 연산도 수행할 수 없다. 따라서 y는 무한대의 값을 가지게 되고 결과로 -1을 리턴하면 된다.

 

x, y의 초기 값이 같다면 어떻게 처리할까?

dp [x]를 통해 해당 값을 0으로 처리하고 있다. 반복문을 살펴보면 x부터 y + 1까지의 값을 처리하며 이 경우 어떠한 연산도 수행할 수 없기에 바로 종료된다. 따라서 dp[x] == dp [y] 이기에 0이 리턴된다.

 

이 코드의 시간 복잡도는 dp를 생성할 때, for문을 돌릴 때 각각 최대 200만 번의 연산을 수행하게 된다. 따라서 시간 복잡도는 O(n)이 된다.

def solution(x, y, n):
    dp = [float('inf')] * (y + 1)
    dp[x] = 0

    for i in range(x, y + 1):
        if dp[i] == float('inf'):
            continue

        if i + n <= y:
            dp[i + n] = min(dp[i + n], dp[i] + 1)

        if i * 2 <= y:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)

        if i * 3 <= y:
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)

    return dp[y] if dp[y] != float('inf') else -1