[백준] 1463번(1로 만들기)

백준 1463번

정답 코드

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

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])

코드 출처

◼ 동적 계획 알고리즘을 사용하여 풀어야 하는 문제

• 문제를 보자마자 동적 계획법을 사용해야 한다는건 감이 왔지만 어떻게 구현하는 건지 감이 오지 않아 다른 사람이 작성한 코드 참고
• 동적 계획법에는 recursive 방법과 iterative 방법이 있는데, 속도와 성능면에서 후자가 유리하다
  출처