[백준_1463] 1로 만들기 python

내일 요코하마 놀러가기로 해서 12시에 미리 풀었는데,

솔브닥 업데이트 시간은 12시가 아니라 6시였다.

그리 어렵지않은 dp문제였으나,

혹자는 처음 봤을 때 그리디 문제로 오해할 수 있는 느낌이 들었다.

또한, n=1일때를 생각하지 못해 처음에는 인덱스 에러가 발생했다.

이는 예외처리로 해결했다.

# n 입력

n = int(input())

# dp 설계

dp = [

　0 for _ in range(n + 1)

]

# n == 1

if n == 1:

　print(0)

# n >= 2

else:

　# dp 초기설정

　dp[2] = 1

　# dp 채워넣기

　for i in range(3, n + 1):

 

　　if i % 3 == 0 and i % 2 == 0:

　　　dp[i] = min(dp[i-1], dp[i//3], dp[i//2]) + 1

 

　　elif i % 3 == 0:

　　　dp[i] = min(dp[i-1], dp[i//3]) + 1

 

　　elif i % 2 == 0:

　　　dp[i] = min(dp[i-1], dp[i//2]) + 1

 

　　else:

　　　dp[i] = dp[i-1] + 1

　# 출력

　print(dp[-1])