pty115   5달 전

점화식은 D[k] = D[k-1] + D[k-2] + D[k-5]인 것까지는 이해했어요

그런데 실제로 구현을 하면 테스트케이스도 오답이 나와요

.

if 동전 액수가 임시 금액 보다 작거나 같다면

D[임시금액] += D[임시금액 - 동전액수]

.

빠뜨린 조건이 있거나, 아니면 로직이 틀린 건가요??

이중 for문 부분이 이상한 것 같아서 바꿔보고 있는데, 잘 안되네요 

pinch3773   5달 전

어떤 문제죠?

pty115   5달 전

저렇게 짜서 돌려보면 1,2,5 동전에 k가 10일때, 결과값이 100이 넘어요

직접 그려봐도 문제가 잘 안보이더라구요 뭔가 중복되는게 있는건지 ㅠㅠ

pty115   5달 전

2293번 문제에요!

pinch3773   5달 전

근데 저렇게 하면 똑 같은 조합이더라도 순서가 다르게 세면 추가적으로 중복 해서 셀거 같은대용.

pinch3773   5달 전

dp[3]을 만드는데 , +=dp[2]을 더하는 경우와 +=dp[1]을 하는 경우에서 각각 (1,2),(2,1)이 두번 세졌겠지요. 

pty115   5달 전

그렇네요!! 중복이 있었네요 ㅠㅠ 잘 처리해봐야겠어요

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