[알고리즘] 1로 만들기 on Python

알고리즘 분류 : DP 다이나믹프로그래밍

 

#import sys

a = int(input("1로 만들 수를 입력하세요 : ")) + 1 #10 입력시 11

min_cnt = [ -1 for i in range(a)] #리스트 내포(List comprehension)기법 #range(0,11) #min_cnt => [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]

for i in range(1,a): #range(1,10)
    min_cnt[i] = min_cnt[i-1] + 1 #minc_cnt[i] = 이전의 minc_cnt값 +1의 값이 저장된다.
    if i % 2 == 0: #i가 2,4,6,8,10일 때 if문 실행하고, min_cnt값과 min_cnt[i/2]+1값을 비교해서 최소값을 저장
        min_cnt[i] = min([min_cnt[i], min_cnt[int(i/2)]+1]) 
    if i % 3 == 0: #i가 3,6,9일 때 if문 실행하고, min_cnt값과 min_cnt[i/2]+1값을 비교해서 최소값을 저장
        min_cnt[i] = min([min_cnt[i], min_cnt[int(i/3)]+1])

print("1로 만들기위해", a-1,"은 2와3으로 나뉘어지는 과정을",min_cnt[-1],"번 거쳐 만들어진다. 소수의 경우 이전 값의 1만들기 최소수 +1이 된 값이다.")

 

 

출처 : https://www.acmicpc.net/