1로 만들기

💻 입력 조건
첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)

💻 출력 조건
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

💻 입력 예시

26

💻 출력 예시

3

📖 문제 해결
전형적인 다이나믹 프로그래밍 유형의 문제로, 보텀업 방식(Bottom-Up) 을 이용하여 2부터 오름차순으로 모든 숫자에 대한 최소 연산의 횟수를 계산해나감으로써 최종적으로 구하고자 하는 숫자에 대한 최소 연산 횟수를 구하였습니다.

# 정수 X를 입력받기
X = int(input())

# 앞서 계산한 결과를 저장하기 위한 DP 테이블 초기화
# 정수 X의 범위가 30000까지이므로 값이 0이고 길이가 30001인 리스트로 초기화
d = [0] * 30001

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
# d[2]부터 차근차근 계산해나감
for i in range(2, x + 1):

	# 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1] + 1
    
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
    	# 1을 빼는 연산과 2로 나누는 연산 중 비교하여 최소 연산 횟수를 가지는 값으로 업데이트
    	d[i] = min(d[i], d[i//2] + 1)
    
    # 현재의 수가 3으로 나누어 떨어지는 경우
    # 1을 빼는 연산과 3으로 나누는 연산 중 비교하여 최소 연산 횟수를 가지는 값으로 업데이트
    if i % 3 == 0:
    	d[i] = min(d[i], d[i//3] + 1)
    
    # 현재의 수가 5로 나누어 떨어지는 경우
    # 1을 빼는 연산과 5로 나누는 연산 중 비교하여 최소 연산 횟수를 가지는 값으로 업데이트
    if i % 5 == 0:
    	d[i] = min(d[i], d[i//5] + 1)

# X의 최소 연산 횟수를 출력
print(d[x])