[일반] 고수님들 도움좀...

[라라귀여운(papipupe)]

https://www.acmicpc.net/problem/2293

이 문제 점화식이

이렇게 되는데 이게 이해가 안감... 어떻게 이렇게 하면 DP[j]가 구해지는거임...??

어제 저녁부터 보고있는데 아무리 해설 찾아봐도 이해가 안감 ㅠㅠ 도움좀..

[하루룽(ailedear)]

그거 원래 2차원 dp인데 메모리 제약 때문에 1차원으로 줄였을거임 ㄱㄷ

[하루룽(ailedear)]

dp[i][j] = i번째 코인까지 사용해서 j를 만들 수 있는 경우의 수라 하면

[하루룽(ailedear)]

dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]] 원래는 이거

[라라귀여운(papipupe)]

근데 그렇게하면 dp[i][j-coin[i]]에서 코인 한번만 쓰는거아님?? 예를들어 10을 5로 만들때 5 두번쓰는경우는 안세어지지않아??

[하루룽(ailedear)]

이전에 dp[i][j-coin[i]]를 계산할 때 dp[i][j-coin[j]-coin[j]]인 경우도 계산했을거아니야

[하루룽(ailedear)]

coin[j]가 아니라 coin[i] 오ㅓ타

[라라귀여운(papipupe)]

아하 그렇구나 발상 쩐다 ㄷㄷ... 알려줘서 고마워 ㄳㄳ