문제

코드

num = int(input())
arr = [0,0]

for i in range(2,num+1):
    #arr[2]부터 2를 나누는것이니깐 1의 값을 가진다 
    # arr[i] = arr[i-1]+1 #1빼기를 선택했을 때의 경우의 수 
    arr.append(arr[i-1]+1)
    if i%3 == 0:
        arr[i] = min(arr[i],arr[i//3]+1)
    if i%2 == 0:
        arr[i] = min(arr[i],arr[i//2]+1)
print(arr[num])

해설

그냥 이프문,,,반복문,,, 해서 3으로 먼저나누고,, 그 다음은 2로나누고,, 안되면 1빼고 이렇게 반복해서 문제를 풀 수 있으리라 생각했는데 10에서 예외가 발생한다.

한번 확인해보자

내가 생각한 방식 : 10->5->4->2->1 : 4번
문제가 생각한 방식 : 10->9->3->1 : 3번

그래서 으으음.. .하고 찾아봤다..!
그러니 Dynamic Programing 이라는 동적계획법을 활용하여야 하는 문제이다
간단히 DP가 무엇인지 설명하자면
가능성을 모두 두고 그 안에서 최솟값을 구하는 것이다 .

그리디 알고리즘과 무엇이 다른가..? 비슷한거 같은데 다르다
그 이유는 그리디 알고리즘은 내가 처음생각한 방식이 옳다!! 생각하고 처음 최적의 방식이 끝까지 예외 없이 적용되는 알고리즘이다 !

그렇다면 이 문제는 어떻게 풀어야하는가 !?

바로 배열 arr을 만들고 그 인덱스 값이 1이 되기 위한 최소한의 숫자를 저장하는 배열이다 그래서 숫자 0과1은 모두 0번이니 0이 저장되서 0으로 초기화 시켜주고
그 이후에는 for문을 이후의 인덱스 값부터 돌면서 값 구해나가는데 1을 빼는 과정을 먼저 거친후 2나 3을 나누었을때의 과정 중 최솟값을 비교해서 그 자리에 넣으면 되기 때문이다 !!

그렇게 Min을 사용해서 최솟값을 초기화시켜주면 마지막에 우리가 구하는 값의 최솟값을 구할 수 있을 것이다.