[파이썬] 백준 1463 1로 만들기

< 처음 풀이 >

접근 방법을 아예 몰랐다. 당연히 3으로 나누면 더 답이 작아지는 줄 알았지만 그렇지 않은 경우가 존재 했다.

 

< 해결 방법 >

동적 풀이 방법을 찾아서 공부를 했다. 처음에는 일해가 되지 않았지만 계속 읽어보니 dp[2], dp[3] ... 순으로의 값들을 저장하는 방법을 알게 되었고 이를 이용해서 해결을 했다. input 이 1 인 경우를 고려하지 않아서 에러가 났지만 스스로 해결을 할 수 있었다.

 

 

import sys
 
a = int(input())
 
if 1<a<3:
    print(1)
elif a==1:
    print(0)
 
# X가 3으로 나누어 떨어지면, 3으로 나눈다.
# X가 2로 나누어 떨어지면, 2로 나눈다.
# 1을 뺀다.
 
else:
    dp = [0]*10000001
 
    dp[2]=1
    dp[3]=1
 
    answer = 0 
 
    for i in range(4,a+2):
        dp[i]=dp[i-1]+1
 
        if i%2==0:
            dp[i] = min(dp[i],dp[i//2]+1)
 
        if i%3==0:
            dp[i] = min(dp[i//3]+1,dp[i])
 
 
 
 
    print(dp[a])