아직 미완성된 코드인점 양해해주시면 감사하겠습니다.

어떻게 알고리즘을 짰냐면,

먼저 입력받은 동전의 가치들을  value 배열에 저장한 다음에 오름차순으로 정리시켰습니다.

그 다음 memo 배열에 입력받은 동전의 가치들을 저장시켰습니다.

그 다음 현재의 가치보다 작은 값들내에서 최고값과 현재 가치의 최고로 큰 약수를 구했습니다.

예를 들어서 현재 가치가 15원이고 동전이 3,5,8원이 있으면 max=8원이고 div=5원입니다.

그리고 이 값들을 이용해 (현재의 가치-max) +1 값과 (현재의 가치/최대로 큰 약수) 값을 비교하려 했습니다.

이대로 코드가 돌아가면, 가치(k)=15원이고 동전이 1.5.12원이 있을 때

dp(15-12)+1 vs 15/5   =>  dp(3)+1 vs 3이고

dp(3)은 다시 dp(2) + 1 / 3        ->       dp(2)= dp(1) +1   /  2이고 그럼 dp(2)=2, dp(3)=3이므로

최초에 dp(3)+1 vs 3가 4 vs 3이 되므로 답은 3이 된다. 대략 이런식입니다.

그런데 이 코드에 문제가 있는게 n=2, k=10이고 n의 종류는 3,4일때 답이 -1이 나옵니다.

왜냐하면 코드 상에서 num<value[i]이면 no_answer=1이 되서 무조건 답이 -1로 출력되는것 떄문에 그런거 같습니다.

위에 예시에서 끝까지 가보면 dp(1)+1 vs 2가 나오는데 dp(1)에서 no_answer=1이 되서 2를 선택할 수 있음에도 불구하고 답이 -1이 됩니다..

그래서 이러한 문제점을 인지하고 코드를 수정해보려 해도 어떻게 수정해야 할지 잘 모르겠습니다ㅠㅠ

결론적으로, 각 분기에서 비교를 할때마다 위에로 치면 dp(1)은 값이 없으므로 무조건 2가 선택되도록 하고 싶은데

어떻게 하면 될까요? 도와주시면 정말 감사하겠습니다.

이외에도, 이 알고리즘이 가진 문제점을 지적해주시면 정말 감사하겠습니다.