1로 만들기2 - 백준 12852 - swift

https://www.acmicpc.net/problem/12852dp를 이용한다. N을 1로 만들기보다는, 1에서 N으로 만드는 경우를 구해본다. dp [ i ] = ( i를 만들기위한 가장 최소경우의수, i를만들기위한 이전의 값 ) 으로 정의한다. i를 만들기위한 이전의값이 필요한 이유는, N까지 가장 빠른 경우의수를 구한다음에, N을 1로 가는 경로들을 dp를 통해 찾아내기 위해서다. dp [ i ] 는 1에서부터 시작하므로, 반대의연산, +1, *2 , *3 3가지경우로 갱신해나간다.각 연산마다 가능한 경우의수가 최소의경우로만 dp[i]를 갱신한다. 예를들어, 6을만들기위해서는, dp[5] + 1, dp[3] * 2 , dp[2] * 3 인경우가있다.dp[5] + 1,인경우는, dp[5]를 만들..........

원문링크 : 1로 만들기2 - 백준 12852 - swift