백준 1463 1로 만들기 (파이썬)

풀이

def solve():
    dp = [0] * (N+1)
    for i in range(2, N+1):
        dp[i] = dp[i-1] + 1
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)
    print(dp[N])


if __name__ == '__main__':
    N = int(input())
    solve()

 

해설

• dp의 인덱스는 그 인덱스 수의 최소 연산을 가지고 있음
• 인덱스 1의 값은 당연히 0이고 2는 1임 (+1 또는 2로 나누기)
• 3가지 경우의 수 중에 가장 적은 연산을 타고올라감