[Algorithm] 백준 BOJ 1463 1로 만들기 : python 파이썬 DP 실버 3

Private 난이도 : ♥♥♥♡♡

1463번: 1로 만들기

n=int(input())
d=[0]*(n+1)
d[1]=0

for i in range(2,n+1):
    d[i]=d[i-1]+1
    if i%3==0:
        d[i]=min(d[i], d[i//3]+1)

    if i%2==0:
        d[i]=min(d[i], d[i//2]+1)
print(d[n])

백준 제출 버전

설명

• 3가지 방법중 1) 1을 빼는 방법 2) 3으로 나누는 방법 3)2로 나누는 방법 으로 이미 계산했던 작은 수들에 대한 결과를 활용하므로써 더 큰 숫자들의 결과를 알 수 있다. 1,2,3 번 방법 모두 그 전 숫자의 결과에 연산을 한 번만 더 하면 되기 때문에 1을 더해주는 것이다
• 어떤 수에는 2로, 어떤 수에는 3으로 나누는 것이 더 효율적일 수 있다는 생각을 할 수 있다. 하지만 처음에 d[i] 자리에 1번 연산을 한 것을 저장해두고 결국에는 if문 2번으로 (else if 가 아닌 if임을 주의) 1,2,3번 중 가장 횟수가 적은 것을 택하기 때문에 상관없다.

배운 점

• 탑다운이 안 될 수도 있다는 것을 알게 되었다.
  처음에 탑다운으로 작성한 코드이다
  

  import sys
  sys.setrecursionlimit(10**6)
  n=int(input())
  
  def makeOne(n):
      # 종료조건
      if n==1:
          return 0
  
      # 메모이제이션
      if d[n]!=0:
          return d[n]
      
      # 재귀 호출
      d[n]=makeOne(n-1)+1
      if n%3==0:
          d[n]=min(d[n], makeOne(n//3)+1)
  
      elif n%2==0:
          d[n]=min(d[n], makeOne(n//2)+1)
  
      return d[n]
  d=[0]*(n+1)
  print(makeOne(n))

  이렇게 했더니 tail recursion에 걸려서 메모리초과가 났다. 그래서 어쩔 수 없이 바텀업 방식으로 할 수 밖에 없었다. 했을 때 메모리초과 나면 무조건 바텀업으로 해야겠다.
• 탑다운에서 바텀업으로 바꾸면서 코드를 복붙했더니 변수명을 끝까지 다 고치지 않아서 틀리는 초보같은 실수를 해서 30분을 날렸다,,