[프로그래머스 파이썬] 숫자 변환하기

def solution(x, y, n):
    answer = 0
    dp = [1e9 for _ in range(y+1)]
    dp[x] = 0

    for i in range(x + 1, y + 1):
        if i//3 >= x and i % 3 == 0 and dp[i//3] != 1e9:
            dp[i] = min(dp[i], dp[i//3]+1)
        if i//2 >= x and i % 2 == 0 and dp[i//2] != 1e9:
            dp[i] = min(dp[i], dp[i//2]+1)
        if i-n >= x and dp[i-n] != 1e9:
            dp[i] = min(dp[i], dp[i - n]+1)

    answer = dp[y]
    if answer == 1e9:
        answer = -1
    return answer

아이디어

처음에는 브루트포스로 while문을 돌려서 해결하려고 했다가 눈치를 챘다. DP다 코인 2, 3, 5로 최소 횟수 세는거랑 비슷한 문제이다.

 

해답

 

- 첫번째 시도

import sys

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

잘 동작하는 것처럼 보이지만 막상 제출하면 50%만 맞추고 다 틀려버린다. 뭔가 이상하다는건 알겠는데 원인을 몰라서 시간이 엄청나게 오려 걸려버렸다.

- 두번째 시도

사실 두번째는 아니고 10번째 시도정도는 되겠다. 내가 코드를 고치다가 0부터 x까지 전부 1e9로 초기화 하는 방법을 시도한 적이 있는데 이 방법으로 3번은 더 틀린거 같다. DP를 사용할 때 주어진 수를 초기화 하는것에 집중해야지 그 전까지 넣으면 로직상 꼬일수도 있다...

- i//3이 정확하게 해당 인덱스를 가르키는지 확인하기 위해 i % 3으로 떨어지는지 확인

- x보다 큰지를 확인하는 것을 넣었는데 지금 보니까 딱히 필요 없는거 같다.

- 다만 체크하는 녀석이 1e9인지 아니면 다른 것인지는 확인해줘야한다. 우리의 연산은 항상 dp[x]에서 출발하는 것이기 떄문에 이 숫자에 근거하지 않으면 안 되기 때문이다.

def solution(x, y, n):
    answer = 0
    dp = [1e9 for _ in range(y+1)]
    dp[x] = 0

    for i in range(x + 1, y + 1):
        if i//3 >= x and i % 3 == 0 and dp[i//3] != 1e9:
            dp[i] = min(dp[i], dp[i//3]+1)
        if i//2 >= x and i % 2 == 0 and dp[i//2] != 1e9:
            dp[i] = min(dp[i], dp[i//2]+1)
        if i-n >= x and dp[i-n] != 1e9:
            dp[i] = min(dp[i], dp[i - n]+1)

    answer = dp[y]
    if answer == 1e9:
        answer = -1
    return answer