DP(다이나믹 프로그래밍): 백준 1463 파이썬

문제:

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이:

이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다.

예를 들어 n=6일 때, 함수가 호출되는 과정을 보면 다음과 같을 것이다. 확인해보면, 마찬가지로 f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다.

이제 문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유는 함수의 호출

횟수를 구해야 하기 때문이다.

이 점화식을 토대로 보텀업 다이나믹 프로그래밍으로 소스코드를 작성하면 정답이 된다.

 

정답:

import sys

n = int(sys.stdin.readline())

d = [0] * 6000001

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])