greedy1

• 

  [c++] 백준- 보석도둑 (Greedy) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제를 처음 봤을 때 완전탐색으로는 아주 쉬운 알고리즘으로 풀 수 있겠다는 생각을 했다. 담을 수 있는 무게가 다른 가방이 여러개 있고 보석의 무게와 가치가 여러개 존재한다면 당연히 보석을 최대한의 가치로 가져가는 방법은 담을 수 있는 무게가 가장 작은 가방부터 최대로 채워가는 것이다. 다시 말하면 가장 담을 수 있는 무게가 작은 가방부터 담을 수 있는 보석 중 가장 높은 가치를 가지고 있는 보석을 차례대로 담아가면 되는 것이다. 이것을 완전탐색으로 풀면 for문을 두 번 돌면서 그냥 이 보석이 이 가방에 담을 수 있는 것인지 아닌지를 판별한다음 담을 수 있다면 담을 수 있는 것 중 가장 가치가 큰 것을 선택해 답에 포함시켜주고 선택된 것을 제외시켜주면.. c++/알고리즘 2023. 2. 5.