2294번 - 동전 2
D[i] = 더해서 i원의 가치가 되는 동전의 최소합
D[i] = D[i%coin] ( i원의 가치에서 현재 금액의 동전을 뺀 나머지 가치) + i/coin (현재 금액의 동전으로 필요한 수)
이런식으로 짯는데 왠만한 경우의 수들은 다 되는거 같은데...
어디가 문제인 걸까요??
2 101
100
1
을 넣어보세요. 답은 2이지만 101이 나오네요.
D[i]를 coin으로 구할 때 필요한 D[x]는 x = i%coin뿐만이 아닙니다.
i%coin보다 큰 금액에서도 얼마든지 coin을 더해 만들 수 있는 경우가 있겠지요 :)
아.. 항상 작은수가 먼저 들어온다고 생각했네요
다시 한번 생각해보겠습니다 ㅋㅋ
zzapcoder님 항상 답변해주셔서 감사해요 ㅋㅋㅋ
댓글을 작성하려면 로그인해야 합니다.
choi0712 9년 전
D[i] = 더해서 i원의 가치가 되는 동전의 최소합
D[i] = D[i%coin] ( i원의 가치에서 현재 금액의 동전을 뺀 나머지 가치) + i/coin (현재 금액의 동전으로 필요한 수)
이런식으로 짯는데 왠만한 경우의 수들은 다 되는거 같은데...
어디가 문제인 걸까요??