BOJ 1463번: 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

아이디어:

조건:

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

dp[i] = min(dp[i-1], dp[i//3], dp[i//2]) #i가 3,2로 나누어 떨어지는 경우..

dp[1]=0, dp[2]=dp[3]=1 

 

n까지 bottom-up 방식으로 반복문을 이용하여 구현하였다.

import sys
n = int(sys.stdin.readline())
dp = [0]*(1000001)
dp[2]=1
dp[3]=1
for i in range(4,n+1):
    a = i%3
    b = i%2
    if (a==0):
        if (b==0):
            dp[i] = min(dp[i-1], dp[i//3], dp[i//2])+1
        else:
            dp[i] = min(dp[i-1], dp[i//3])+1
    else:
        if (b==0):
            dp[i] = min(dp[i-1], dp[i//2])+1
        else:
            dp[i] = dp[i-1]+1
print(dp[n])