Greedy알고리즘 이란? 🎯최적의 값을 구해야 하는 상황에서 사용된다. 🎯각 단계에서 최적이라고 생각되는 방법으로 값을 반환해 나가는 방식이다. 🎯주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적의 답을 구한 뒤 이를 결합하여 전체 문제의 최적의 값을 구하는 경우 사용한다. 쉽게 말해서 규칙을 파악하고 그 규칙을 메서드화 한 후 반복수행하여 값을 구하는 방식이라고 할 수 있다. 위 문제에서 규칙을 파악하기 위해 예시를 봐보자. 예상해볼 수있는 규칙 1. 4200원보다 큰 숫자는 무시해도 된다. 2. i>=2인 경우에는 A의i번째는 Ai-1의 배수라고 하였다. 각 숫자들은 배수관계라는 것을 알 수있다. 예를 들어 10(A의 3번째)은 5(A의 2번째)의 배수이다. 우리는 최소한의 연산..