Greedy3 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. 1541 잃어버린 괄호 그리디 알고리즘으로 푸는 문제이다. 괄호를 무한히 맘대로 사용할 수 있다. -가 나온 뒤에 +가 나온다면 다 괄호로 묶고, -가 나온다면 새로 괄호를 시작하여 뒤에 +를 다 묶으면 된다. 즉 -가 나오면 그냥 다 빼주면 된다. 그 순간의 최적해가 전체의 최적해가 되는 구조인 문제. 논리적으로 이게 정답이 나올지 잘 생각해보아야 한다. 그게 보장이 된다면, greedy algorithm으로 해를 구할 수 있다. +는 상관없이 계속 더하면 되지만, -가 나오면 그 다음으로 나오는 수는 다 빼주면 된다. #include using namespace std; int main() { string s; getline(cin, s); bool minus_check = false; int start = 0; int a.. 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 다음
