네 번째 문제
Berry Picking
@USACO
문제를 요약하면, n개의 나무에 각각 다른 수의 열매가 열린다. 그리고 k개의 바구니에 열매를 담는다. 서로 다른 나무의 열매를 하나의 바구니에 담을 수 없고, k/2 만큼의 수의 바구니를 그것도 가장 양이 많은 것부터 언니에게 준다. 동생이 가질 수 있는 최대값을 구하여라.
Input - 나무 수 N, 열매들 Bs, 바구니 수 K
Output - 최댓값
(정답을 참고하여)
나는,
각 나무에 열린 열매 수에 담고자 하는 열매 수를 나누고, 몫을 모두 더한 것이 각 바구니에 담겨있는 열매의 수가 된다는 방식으로 문제를 풀었다.
예를 들어,
바구니가 총 4개이고 5개의 나무에 각각 3, 6, 8, 4, 2개의 열매가 있다고 하면, 4개의 바구니에 모두 담으면서 최대로 담을 수 있는 열매의 수는 4번째로 큰 3이다.
하지만, 더 많은 열매를 담으려면 8개를 열매를 가진 나무에서 4개씩 두 바구니, 그리고 나머지 나무에서 4개를 바구니에 담으면 가능하다.
(1)
(Input) 3 6 8 4 2 -> (정렬) 2 3 4 6 8 -> (선택) 2 3 4 6 8 ---> 3보다 큰 4 가능?
(가능) 2 3 4 6 (4 4)
(2)
(Input) 3 6 8 4 2 --> 1부터 최대 8까지 각각 나누고 몫의 합
(3으로) 6 -> (4로) 4 -> (5로) 2 (절반 바구니 다 뺏김 끝. 지금까지 최대)
즉, 각 나무 열매 수에 4를 나눈 몫을 모두 더하는 것이다.
그리고 나서 나머지에 따라 정렬 후, 본인이 받을 나머지를 더해서 최종적으로 얻을 수 있는 열매의 수를 구하였다.
어려웠던 점
몫을 모두 더한다는 수학적인 센스가 없어서 결국 몇개의 테스트만 성공시키다가 답을 확인하게 되었다.
수학적인 센스가 경험이 더욱 필요하다고 느낀다.
내 코드
끝 🙋♂️
