[백준] 1463 1로 만들기

요약

처음에 2차원 배열로 풀이를 작성하였지만 시간초과였습니다. 1차원 배열의 Bottom-UP 방식의 배열을 1회 순회하는 코드를 작성하여 문제를 해결하였습니다. 이전 단계에서의 최솟값을 어떠한 값을 기준으로 해야 하는 지 아는 것이 문제의 핵심으로 보입니다. 제가 이전에 풀었던 설탕 배달 문제와 유형이 동일합니다.

 

솔루션

python3 으로 솔루션을 작성하였습니다.

def getMin(n):
    
    '''
    e.g n==10일때
    0    1    2    3    4    5    6    7    8    9    10
    0    0    1                                  2    3
    '''
    dp = [0 for _ in range(n+1)]
    dp[1] = 0
    
    for index, value in enumerate(dp):
        if index == 0 or index == n:
            continue
        if index+1 <= n:
            if dp[index+1] == 0 or value+1 < dp[index+1]:
                dp[index+1] = value+1
        if index*2 <= n:
            if dp[index*2] == 0 or value+1 < dp[index*2]:
                dp[index*2] = value+1
        if index*3 <= n:
            if dp[index*3] == 0 or value+1 < dp[index*3]:
                dp[index*3] = value+1

    return dp[n]

N = int(input())
answer = getMin(N)
print(answer)