[Python/백준] 1463번 : 1로 만들기 (DP : dynamic programing)

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

1463번: 1로 만들기

풀이 (dp로 풀어야됨)

def make_one(n : int) :
    dp = [0] * (n+1)
    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)
    return dp[n]

if __name__ == '__main__' :
    n = int(input())
    print(make_one(n))

 

dp 점화식

- 최초에 n이 1일 때의 연산값은 0임. (dp[1] = 0)

- n이 2일 때의 연산값

1. n에서 1을 빼고(우선) n-1의 연산 값(memorization)을 더한 값 (dp[2] = dp[2-1] + 1)

2. n을 2로 나누고(우선) n//2의 연산값(memorization)을 더한 값(dp[2] = dp[2//2] + 1)

을 비교(min(dp[2-1]+1, dp[2//2] + 1)

- n이 3일 때의 연산값

1. n에서 1을 빼고(우선) n-1의 연산 값(memorization)을 더한 값 (dp[3] = dp[3-1] + 1)

2. n을 3으로 나누고(우선) n//3의 연산 값(memorization)을 더한 값 (dp[3] = dp[3//3] + 1)

을 비교(min(dp[3-1]+1, dp[3//3] + 1)

- n이 4일 때의 연산값

1. n에서 1을 빼고(우선) n-1의 연산 값(memorization)을 더한 값 (dp[4] = dp[4-1] + 1)

2. n을 2로 나누고(우선) n//2의 연산 값(memorization)을 더한 값 (dp[4] = dp[4//1] + 1)

을 비교(min(dp[4-1]+1, dp[4//2] + 1)

...

- n이 6일 때의 연산값

1. n에서 1을 빼고(우선) n-1의 연산 값(memorization)을 더한 값 (dp[6] = dp[6-1] + 1)

2. n을 2로 나누고(우선) n//2의 연산 값(memorization)을 더한 값 (dp[6] = dp[6//2] + 1)

2. n을 3으로 나누고(우선) n//3의 연산 값(memorization)을 더한 값 (dp[6] = dp[6//3] + 1)

을 비교(min(dp[6-1]+1, dp[6//2] + 1,  dp[6//3] + 1)

...

해당 방식을 반복 수행함