백준 2293번 동전 1 문제 해설/풀이/코드 (파이썬) 다이나믹 프로그래밍 활용..!

코드만 궁금한 분은 깃허브링크

GitHub - Rhyankwon/algorithms

 

문제 이해는 쉽다.

10이 있고, 1원 2원 5원짜리 동전이 있으면 그 동전들을 막 조합해서 10을 만들면 되는데, 그렇게 10이 되는 주어진 동전들의 조합의 총 갯수를 반환하면 된다.

 

간단한 다이나믹 프로그래밍이다. 1부터 10까지 가능한 동전의 조합 수를 dp라고 하자.

 

우선 위에 내가 서술한 문제로 보면, dp[10]은 dp[9] + dp[8] + dp[5]이다. 왜냐면,  9까지 만든 다음 거기에 1원짜리 동전 하나를 더하고, 8까지 만든다음 거기에 2원짜리 동전 하나를 더하고, 5원까지 만든다음 거기에 5원짜리 동전을 하나 더하면 되기 때문이다.

 

그런데 여기서 주의할 점은, 1원 -> 2원 -> 5원 순서대로 해야한다는 점이다. 이게 무슨 말이냐면, 1원만으로 가능한 조합의 수를 먼저 계산하고, 2원 5원을 추가하는 식으로 해야한다는 말이다. 그렇게 해야 경우의 수를 생각할때 섞이지 않는다. 손으로 써보면서 하면 조금 더 이해가 된다. 

 

dp는 풀어도 풀어도 잘 생각이 안나는게 문제인것같다.. 연습 많이 해야지뭐