[dp/백준] 1463번: 1로 만들기(2차)

-문제: https://www.acmicpc.net/problem/1463

 

거의 3번째로 푸는 문제인데, 또 못 풀었다 이번에는 꼭 풀이 다 이해하고, 작성까지 연습하고 가야겠다 

n이라는 숫자는 n-1에서 1을 더하거나, n//2에서 2를 곱하거나, n//3에서 3을 곱한 경우가 있다 

따라서 점화식으로는 dp[n]=min(dp[n//3]+1,dp[n//2]+1,dp[n-1]+1)인데, 이를 그대로 이용하는 것이 아니라 

n이 3의 배수인 경우와 2의 배수인 경우를 나눠서 dp[n-1]+1과 비교해야 한다 

n이 모두 2와 3의 곱으로 이루어진 경우는 없지만, n-1에서 +1이 된 경우는 있기 때문이다. 

따라서 정답풀이를 작성하면 다음과 같다 

 

for문의 범위가 2부터 시작하는 이유는

1부터 시작한다면 dp[1]==1이고, dp[2]==2가 되므로 틀리기 때문이다. 

문제는 1까지 가는 경우의 수를 말했으므로, dp[1]==0이어야 한다 그래야 dp[2]==1이 된다 

 

여전히 다 풀지 못했지만, 적어도 풀이가 이해가 가서 조금이라도 발전했다

n=int(input())
dp=[0 for _ in range(n+1)] 

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

위의 풀이는 정답인데, 왜 밑에 풀이는 정답이 아닌지 모르겠다 그냥 같은거 대체한 거 아닌가??

n=int(input())
dp=[0 for _ in range(n+1)] 

for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    if i%2==0 :
        dp[i]=min(dp[i//2]+1,dp[i-1]+1) #여기와
    if i%3==0 :
        dp[i]=min(dp[i//3]+1,dp[i-1]+1) #여기만 다르다
        
print(dp[n])