Exchange Problem문제 질문있습니다.

이 문제를 분석하다가 어려워서 질문드립니다.

제가 분석한 결과는 dp를 통해 모든 경우의 수를 구한 것과 그리디를 통해 구한 경우의수를 비교하는 문제 같았습니다.

근데 예시를 보고 어떻게 문제를 접근해야하는지 모르겠습니다.

8
1 5 10 50 100 500 1000 10000

위의 예시처럼 밑의 8개의 단위로 된 동전을 통해서 모든 단위(1원~9999원)의 동전에 대해 그리디가 맞다면 yes이고 아니면 no를 택하는것인가요?

너무 어렵습니다... 혹시 파이썬 답안을 알려주실 수 있으신가요? 아니면 추가적인 강의에 대한 생각이 있으신지도 궁금합니다.