탐욕법. [5585 / 2217]

[1. 문제 설명]

[2. 풀이 접근]

== 문제 5585 ==

거스름돈이 500엔이고 이때, 거스름돈 동전 개수를 최대한 적게 주는 경우를 생각해보면,

500 엔을 하나 주면 된다.

즉, 거스름돈을 최대 한 큰 금액부터 주면 된다.

== 문제 2217 ==

처음에는 이분 탐색으로 접근해보았다.

w 의 최소는 1이고, 최대는 (9,999*100,000)

로프를 중량 한도 순으로 정렬하고, 여기서 count 개 선택하는 경우를 따져본다.

그런데 중요한 점은 count = 3 일 때, 앞에서 부터 선택하는 것이아니라

뒤에서 부터 선택하는 것이 항상 더 낫다는 것이다.

문제에서 원하는 것은 k 개의 로프를 선택했을 때 버틸 수 있는 최대 중량이다.

k 개를 선택하면 결국 이 중 최소 값에 가장 큰 영향을 받는다.

그렇기 때문에 정렬 상 앞쪽에오는 것들은 중량 한도가 낮으므로, 굳이 선택 할 필요가 없다는 것이다.

결국, 이분 탐색 까지 고려할 필요는 없었다.

[3. 코드 - 5585]

[3. 코드 - 2217]

test_kernelv2