그냥 10이 주어지면 /3 또는 /2 또는 -1 셋 중에 하나의 연산을 써서 1로 만드는 거에요 그런데 거기서 연산의 횟수를 최소화하는거죠
점화식 세우는 방법은 dp[n][3] 배열을 선언한뒤에
dp[n][0] 은 dp[n*3][0] , dp[n*3][1] , dp[n*3][2] 중의 최솟값+1
dp[n][1] 은 dp[n*2][0] , dp[n*2][1] , dp[n*2][2] 중의 최솟값+1
dp[n][2] 은 dp[n+1][0] , dp[n+1][1] , dp[n+1][2] 중의 최솟값+1
이렇게 두고 푸시면 됩니다.
즉 0 은 *3 으로 들어온 것 중 최솟값을 나타내고 1 은 *2 들어온것 중 최솟값 2 는 +1로 들어온것 중 최솟값이죠
rudxo007 7년 전
제가 이해하고 있는 부분이 input 값을 받아서 그 값을 /3 이나 /2 나 -1 을 통해
결과값 1을 만드는데 연산횟수가 가장 적게 해서 하는 거라고 이해 하고 있습니다.
예를 들어 10이면
10/2 = 5
5-1 = 4
4/2 = 2
2/2 = 1
정답은 아니지만 4번으로 1이 만들어졌는데 중복으로 /3 이나 /2나 -1을 사용해도 상관 없는건가요??
그리고 점화식이 생각이 나질 않습니다 점화식 세우는데 있어서 도움 주시면 정말 감사드리겠습니다!!!!