[프로그래머스] 숫자 변환하기 [python]

문제

문제는 간단했다.

x를 더 큰 수로 만들 수 있는 방법은 3가지 있고, y라는 target 수에 도달하는 방법 중 최소 연산을 한 값을 구하는 거 였다.

DP로 풀었다.

memorize로 값들을 1억으로 초기화를 했고, 시작하는 수인 x를 0으로 설정하고, 세가지 연산을 진행하였다.

현재 계산하는 값이 1억이면 도달할 수 없는 수 이기 때문에 넘어가고, 현재까지 도달하는 데 연산 수 + 1 과 도달할 수에 저장된 값을 비교하여, 작은 값을 현재 연산 수로 저장하였다.

 

코드

def solution(x, y, n):
    answer = 0
    memorize = [1e9] * (y+1)
    memorize[x] = 0
    for i in range (x, y+1):
        if memorize[i] == 1e9:
            continue
        if i + n <= y:
            memorize[i+n] = min(memorize[i+n], memorize[i] + 1)
        if i * 2 <= y:
            memorize[i*2] = min(memorize[i*2], memorize[i] + 1)
        if i * 3 <= y:
            memorize[i*3] = min(memorize[i*3], memorize[i] + 1)
    
    if memorize[y] == 1e9:
        return -1
    return memorize[y]