[다이나믹 프로그래밍] -1로 만들기

정수 X가 주어질 때 아래와 같은 4가지 연산을 사용할 수 있다.

첫번째, 5로 나누어 떨어지면 5로 나눈다

두번째, 3으로 나누어 떨어지면 5로 나눈다.

세번째, 2로 나누어 떨어지면 2로 나눈다.

네번째, x에서 1을 뺸다.

 

위 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라.

 

입력예시)

26

 

출력예시)

1

 

 

나의 코드

못품..

꽤나 많은 시간 그림과 함께 이것저것 생각해 보았지만 구현 실패...으악

 

 

 

정답 코드

X=int(input())

dp=[0]*(X+1)

for i in range(2,X+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)
    if i%5==0:
        dp[i]=min(dp[i],dp[i//5]+1)
        
print(dp[X])

음.. 아직 다이나믹적 사고가 잘 안되는것 같다..

아래가 그림이 최종적인 dp 테이블을 채우는 로직인데 나도 여러 그림을 그리면서 접근을 해보려 했지만 아래와 같은 흐름은 생각 하지 못했다..

dp(n)=min(dp(n//2),dp(n//3),dp(n//5),dp(n-1)) +1 이 최종 적인 점화식이다. 

(단, dp(n//2),dp(n//3),dp(n//5)가 각각 존재할 경우.)