12852

편집 시간: 2022년 4월 1일 오후 4:34

코드

f(N)이 N을 1로 만들기 위해 최소 연산 수라고 가정하면 아래의 식을 만족한다.

$$ f(N)=min(\space f(N/3),f(N/2),f(N-1) \space) +1 $$

위 점화식을 이용해 바텀업으로 dp를 구현하면 쉽게 최소 연산 수를 구할 수 있다.

추가적으로, 자신이 선택한 경로를 저장해두면 연산 과정도 쉽게 구할 수 있다.