1, 2, 5원짜리 세개의 동전으로
가장 적은수의 동전으로 교환해주는 경우를 생각해보면
1원 사용하고 다음레벨에서 1원사용하고 ...
전위순회로 도달하는 가장 첫번째 말단노드는 1111...이 되고
가장 마지막 말단노드는 5555...가 되므로
중복순열과 비슷하게 동전교환도 같은 동전을 사용할 수있다
동전의 종류만큼 상태트리의 가지가 생기고
동전의 사용 갯수+1(DFS(0)포함)만큼 레벨이 생긴다
경우의수가 너무많아질 수 있어서 내림차순으로 정렬하고
큰 단위의 동전이 작은단위의 동전보다 먼저 가지가 생기도록 한다
해당 댓글은 삭제되었습니다.
해당 댓글은 삭제되었습니다.