choi0712   9년 전

D[i] = 더해서 i원의 가치가 되는 동전의 최소합

D[i] = D[i%coin] ( i원의 가치에서 현재 금액의 동전을 뺀 나머지 가치) + i/coin (현재 금액의 동전으로 필요한 수)

이런식으로 짯는데 왠만한 경우의 수들은 다 되는거 같은데...

어디가 문제인 걸까요??

zzapCoder   9년 전

2 101

100

1

을 넣어보세요. 답은 2이지만 101이 나오네요.

D[i]를 coin으로 구할 때 필요한 D[x]는 x = i%coin뿐만이 아닙니다.

i%coin보다 큰 금액에서도 얼마든지 coin을 더해 만들 수 있는 경우가 있겠지요 :)

choi0712   9년 전

아.. 항상 작은수가 먼저 들어온다고 생각했네요

다시 한번 생각해보겠습니다 ㅋㅋ

zzapcoder님 항상 답변해주셔서 감사해요 ㅋㅋㅋ

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