프로그래머스 숫자 변환하기 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

문제의 3가지 연산을 통해 y를 만들기 위한 방법은 아래 중 하나이며, 최소 연산을 구하기 위해서는 아래 세 가지 경우 중 가장 적은 연산의 수에 1을 더하면 된다. 

y를 만들 수 있는 방법
1. [y-n] + n = y
2. [y/2] * 2 = y
3. [y/3] * 3 = y

 

이전 수를 통해 다음 수의 최소 연산을 구할 수 있기 때문에 이를 점화식을 정의하고 표현할 수 있고, 해당 점화식을 통해 DP로 구현할 수 있다.

점화식 정의
d[i] = 숫자 i 를 만들 수 있는 최소 연산 횟수

점화식
d[i] = max (
                d[i-n]+1, if d[i-n] != INF
                d[i/2]+1, if i%2 ==0
                d[i/3]+1, if i%3 ==0
            )

 

 

시간 복잡도

메모제이션을 위해 x+1 부터, y 까지 for문을 돌며 순회하기 때문에 O(n)이 걸리며, y의 최댓값이 1e6이기 때문에 시간 내에 동작한다.

 

 

코드

INF = int(1e7)

def solution(x, y, n):
    d = [INF] * (y + 1)

    # d[i] = x -> i 로 만들기 위한 최소 연산 횟수
    d[x] = 0
    for i in range(x + 1, y + 1):
        compare = []

        # i보다 n 작은 수로 부터 연산이 가능하다면, d[i-n]값에 1을 더한다.
        compare.append(d[i - n] + 1) if d[i - n] != INF else compare.append(INF)

        if i % 2 == 0:  # 2를 곱하기 전 수가 존재한다면 해당 d 값에 1을 더해서 추가한다.
            compare.append(d[i // 2] + 1)

        if i % 3 == 0:  # 3를 곱하기 전 수가 존재한다면 해당 d 값에 1을 더해서 추가한다.
            compare.append(d[i // 3] + 1)

        # n번째 전, /2 , /3 번째 수 중 최소 연산을 선택해서 저장한다.
        d[i] = min(compare)

    answer = d[y]
    if d[y] == INF:  # INF 인 경우 만들 수 있는 경우가 존재하지 않는 것 -> -1 출력
        answer = -1
    return answer