[백준] 1로 만들기 1463번 (PYTHON)

✔ 문제 1463 1로 만들기

문제 바로가기 💨 

 

핵심 아이디어

꽤나 헤맸던 문제이다... dp 너무 어렵다 ㅠㅠ정복하겠어!!!

일단 주어진 숫자의 최소 연산값을 구할때, 이전숫자는 -1,//2,//3중하나이다.

이때, 만약 주어진 N이 6이라 가정해보자. 그럼 6 이전의 계산값은 5,3,2 중하나일 것이다.

그러면 5,3,2중의 최소연산값중 가장 작은 최소연산값에 + 1을하면, 6의 최소연산값이 된다.

문제는 이러한 아이디어에서 착안한다.

N까지의 숫자의 최소연산값을 구한다.배열 인덱스를 두고, 이전 연산을 바탕으로 -1을했을때,//2 했을때, //3 했을때의 최소연산값을 계속 구해 나간다.

 

 

PYTHON

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%2==0: # 숫자가 2의 배수인 경우 (*2)
        dp[i] = min(dp[i],dp[i//2]+1)
    if i%3==0: # 숫자가 3의 배수인 경우 (*3)
        dp[i] = min(dp[i],dp[i//3]+1)
ans = dp[N]
print(ans)