백준 1463 - 1로 만들기.py

다이나믹 프로그래밍이란?

똑같은 계산을 반복하지 않기 위해서, 한 번 계산한 값을 메모리에 저장하였다가, 그 계산이 필요할 때 가져다 쓰는 방법

> 불필요한 반복계산을 줄여서 시간효율이 높아진다.

 

백준 1463번

숫자 x를 입력으로 받는다.

1. 3으로 나누어지는 수라면 3으로 나눈다.

2. 2로 나누어지는 수라면 2로 나눈다.

3. 1을 뺸다.

 

이 세 가지 연산을 적절히 사용해서 최소 계산 횟수로 최종 1을 만드는 문제.

 

만약 입력이 10이라면

f(10) > f(9), f(5)

f(9) > f(8), f(3)