[백준]1463번 1로 만들기

 

 

해당 문제는 DP 문제 입니다.

 

접근법

- 작은 문제로 나눴을 때 이번 값을 중복해서 사용할 수 있음

- 메모리제이션 활용

- 이전 dp를 활용하여 값 계산

- 3과 2로 나누어 떨어질 경우 : 최솟값 계산

      1) 이전 dp 활용

      2) 3과 2로 나누어지는 dp 활용

 

연산 조건를 한번 더 생각해 볼 필요가 있었습니다.

연산 조건의 우선순위를 다시 생각해봤으면 좀 더 빠른 풀이가 가능했을 것 같습니다.

 

x = int(input())
dp = [0] * (x+1)

def func_dp(n):
    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)
            
func_dp(x)
print(dp[x])