dmsgh7678   10달 전

배열을 하나 만들어서 약간 dp를 만드는 식으로 접근했는데 맞는지 모르겠네요,....

이런식으로 했는데 error가 뜨네요..ㅠㅠ 

도대체 어디가 문제일까요??

웬만한 data들을 다 넣어 봣는데 틀린점을 모르겠습니다...

도와주세요... 

그리고 최소값 구하는 DP인가?? 동적 다이나믹 프로그래밍에서 쓰는 거 약간 이런식으로 하는거 맞나요????

indioindio   10달 전

배열로 구현하셨지만 저는 일단은 재귀적으로 설명해드리겠습니다.
f(n)을 n을 1로 만드는 데 드는 최소값이라고 정의한다면, (구현이 어떻게 되어 있는지는 모르겠지만 무조건 그런 답을 내줍니다)
f(n) = min(f(n-1), f(n/2), f(n/3)) + 1 이라고 할 수 있겠죠. (n-1, n/2, n/3중에서 정수가 아니면 제외하고요)
다만 이걸 그대로 계산하면 중복된 계산이 여러 번 있게 됩니다. 그래서 재귀함수의 계산 결과를 배열에 저장해놓고 배열에 그런 값이 있으면 불러오는 식으로 계산 횟수를 줄일 수 있습니다.
근데 이걸 배열로 하고자 한다면, num[i]를 i를 1로 만드는 데 드는 최소값이라고 정의하고, 위의 재귀식을 참고하여 하신 것처럼 4에서 n까지 쭉 올라가시면 될 것 같네요
위의 재귀식은 n부터 시작해서 쭈욱 내려가다가 base case인 0, 1, 2, 3을 만나면 그 값으로 부터 다시 올라온다면, 배열은 base case부터 시작해서 올라간다는 차이점이 있겠네요

dmsgh7678   10달 전

그러면 알고리즘 적으로는 틀린게 없다는 거죠?? ㅠ

indioindio   10달 전

16은 16 - 8 - 4 - 2 - 1로 4번에 만들 수 있는데 위의 알고리즘은 16-1 % 3 == 0인 바람에 (10 - 1 = 9 를 최적화하려고 넣으신 조건인 것 같은데 16일 때는 또 성립하지가 않죠) 16 15 ....으로 5번이 걸리는 것 같네요

indioindio   10달 전

숫자의 형태를 보고 뭐가 최소일지 알아내서 계산하시기 보다는 위의 식을 참고하셔서 가능한 경우를 구해본 다음 그 중에서 최소값을 고르는 식으로 하시면 좋을 것 같아요

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