그리디2 2217 로프 greedy 로 풀어봅시다. 예를 들어 로프의 정보가 다음과 같이 주어졌다고 합시다. 20 8 15 9 2 먼저 내림차순으로 정렬한 뒤, (그렇지 않으면 그리디하게 풀 수 없습니다.) 20 15 9 8 2 생각해봅시다. 1) 20 ans = 20 2) 20 15 현재 만들 수 있는 최대 중량 = 20 바뀐 최소 값(15)으로 만들 수 있는 최대 중량 = 30 ans = 30 3) 20 15 9 현재 만들 수 있는 최대 중량 = 30 바뀐 최소 값(9)으로 만들 수 있는 최대 중량 = 9 * 3 = 27 ans = 30 4) 20 15 9 8 현재 만들 수 있는 최대 중량 = 27 바뀐 최소 값(8)으로 만들 수 있는 최대 중량 = 8 * 4 = 32 ans = 32 5) 20 15 9 8 2 현재 최소인.. 2019. 7. 25. Greedy 알고리즘 11047가 동전 0 1. 예제 - { 1 5 10 50 100 500 1000 5000 10000 50000 } 이 있을 때, 4200원을 만드는 최소의 방법은 1000 * 4 + 100 * 2 이므로 총 6회이다. 2. 문제해결 - [그리디한 해결전략] 순간의 최적해를 구한다. (위 문제는 순간의 최적해가 최종 문제의 정답의 최적해인 경우라서 문제가 해결된다.) 가치가 가장 큰 동전을 최대한 많이 이용하고, 같은 방법으로 나머지 금액을 가치가 가장 큰 동전을 최대한 많이 이용해서 금액을 다 채울때 까지 반복한다. 2019. 7. 14. 728x90 이전 1 다음
