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을 사용해도 상관 없는건가요??

그리고 점화식이 생각이 나질 않습니다 점화식 세우는데 있어서 도움 주시면 정말 감사드리겠습니다!!!!

dtc03012   7년 전

그냥 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로 들어온것 중 최솟값이죠

dtc03012   7년 전

for 문은 n -> 1 로 돕니다

rudxo007   7년 전

감사합니다. 코드를 짜보고 다시 질문 드리겠습니다.

댓글을 작성하려면 로그인해야 합니다.