[백준][Python] 1463번 1로 만들기

1463번: 1로 만들기

 

코드

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

 

설명

2나 3으로 나누어떨어지더라도 1을 먼저 빼주는 것이 최솟값이 될 수 있으므로 모든 경우의 수를 생각해야 한다.

먼저 dp[i]의 값을 1을 먼저 빼줬을 경우의 횟수인 dp[i-1]+1로 둔다. 그다음 만약 i가 3으로 나누어떨어지면 i를 3으로 나눈 값의 최솟값에 1을 더한 값을 dp[i]와 비교하여 더 작은 값으로 바꿔준다. 2로 나누어떨어질 때도 마찬가지다.