[백준] 1463: 1로 만들기 (Python)

문제📖

풀이🙏

• 구하고자 하는 n값의 1로 만드는 가장 짧은 연산수를 찾기위해 bottom-up 방식으로 낮은 dp부터 구한다.
• 먼저 1을 빼는 경우는 d[i] = d[i-1]+1 통해 i-1의 dp값 + 1로 연산수를 초기화한다.
• 만일 2로 나눠진다면

    # 현재의 수가 2로 나누어 떨어지는 경우
    if i%2 == 0:
        d[i] = min(d[i], d[i//2]+1)`를 통해 초기화한다.

• 만일 3로 나눠진다면

    # 현재의 수가 3로 나누어 떨어지는 경우
    if i%3 == 0:
        d[i] = min(d[i], d[i//3]+1)

코드💻

n = int(input())

d = [0] * (n+1)

# 다이나믹 프로그래밍(DP) 진행 bottom-up
for i in range(2, n+1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1]+1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i%2 == 0:
        d[i] = min(d[i], d[i//2]+1)
    # 현재의 수가 3로 나누어 떨어지는 경우
    if i%3 == 0:
        d[i] = min(d[i], d[i//3]+1)
    
print(d[n])