[백준] 알고리즘 C++ 1463번 - 1로 만들기 문제

다이나믹 프로그래밍 DP 를 이용하여 풀 수 있습니다.

dp[1] = 0 

dp[2] = 1 // 2로 나누어 1로 만들어짐

dp[3] = 1 // 3으로 나누어 1로 만들어짐

dp[4] = 2 // 2로 나누고 -1 총 2번

dp[5] = 3 // 1빼고 dp[4] 의 값 총 더해서 3번

즉 dp[n]=dp[n/2]+1 , dp[n/3] +1, dp[n-1] +1 이 셋중 최소 값을 찾는 것이 최단 수 이다.