안녕하세요! 왜 +1 을 하는 지 모르겠습니다

Question

안녕하세요! 좋은 강의 감사합니다

동전문제 구현 5:13초에서요~

dp[i] = max(dp[i - 3] + 1, dp[i - 5] + 1);

dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);

위 두 문장에서 왜 +1 이 쓰이는 지 모르겠습니다ㅠ

도와주시면 감사하겠습니다!ㅎㅎ

Answer

안녕하세요 허수정님. 답변 드리겠습니다.

1. DP[i]는 i원을 지불하기 위한 동전의 최소 개수를 의미합니다.

2. DP[i-3], DP[i-5]는 각각 i-3, i-5원을 지불하기 위한 동전의 최소 개수를 의미합니다.

3. DP[i-3] + 1, DP[i-5] + 1은 각각 i원을 지불하기 위한 동전의 최소 개수를 의미합니다.

결국, 대괄호 [ ] 에 들어있는 숫자는 i원을 지불하기에 3원, 5원이 부족한 금액을 의미를 합니다. 따라서, 각각 3원/5원 동전을 1개 추가로 (+1) 사용하여 동전의 개수를 센 것입니다.

허수정님이 만족하시는 답변이 되었기를 바라며, 답변 해결로 상태 변경을 부탁드립니다.

이후에도 문제를 풀거나 공부하시면서 어려운 점이 있다면 질문 올려주세요.

마지막으로, 감사의 말씀을 전하며 답변을 마칩니다.