[1463번]1로 만들기 코딩

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

코딩

import sys
n=int(sys.stdin.readline())

def makingOne(num):
    tmp=0
    ret=[0,0,1,1]
    if num<4:
        print(ret[num])
    else:
        for x in range(4,num+1):
            tmp=ret[x-1]+1
            if x%2==0:
                tmp=min(tmp,ret[x//2]+1)
            if x%3==0:
                tmp=min(tmp,ret[x//3]+1)
            ret.append(tmp)
        print(ret[num])
    
makingOne(n)

---

-처음에는 입력받는 n에서부터 하향식으로 하려고 생각하고 구상을 했지만 도저히 답이 안나올거 같았다. 여러 갈래로 도달 할 수 있는데 각자 다 구하고나서 최소값을 비교하면 비효율적이고 구현도 어려워서 반대로 밑에서부터 올라가는 방법을 생각했다.

-결국 최소값을 구할 때는 경우에 수를 모두 구하고 난 후 비교를 할 수도, 과정을 거치면서 그때마다 최소인 값을 구해서 나아갈 수도 있음을 배울 수 있었다.

-메모리에 n까지 최소값을 메모이제이션하면서 구하는 방법이 처음에는 메모리 낭비가 심할 것으로 판단해서 제외하고 고민했지만 결국 이 방법으로 하게되었다. 다른 좋은 방법이 없을지 고민해봐야지..ㅎㅎ