20. 스까마시자!

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

컴공이는 음료수를 섞어마시기를 좋아한다.

섞어마신다고 해도 아무렇게나 먹는 것은 아니고, 당도가 \(K\) 이상인 음료수만 마시고 싶어한다.

컴공이가 준비해둔 음료수는 모두 \(N\)종류이고, 부피는 모두 \(1\)로 동일하다.

음료수의 당도는 (당분의 총합 / 음료수의 총 부피)으로 계산한다.

초기에 \(N=3\)에 대한 음료수의 당분이 \([2, 3, 1]\)로 주어졌다면

첫 번째 음료수의 당도는 \(2 / 1 = 2\) 이고,

첫 번째 음료수와 두 번째 음료수를 섞으면 당도는 \((2 + 3) / 2 = 2.5\)가 된다. 셋을 모두 섞으면 당도는 \((2 + 3 + 1) / 3 = 2\)가 된다.

컴공이는 자기가 갖고 있는 음료수를 섞어서 최대한 많은 양의 음료수를 마시고 싶다.

가령, \(N = 4\), \(K = 3\)이고, 음료수의 당분이 \([1, 3, 5, 1]\)로 주어지면,

\(1, 2, 3\)번 음료를 섞어서 마시면 당도가 \(3\)이고 부피가 \(3\)인 음료수를 만들어 먹을 수 있지만,

네 음료수를 모두 섞으면 당도가 \(2.5\)가 되므로 최소 당도를 만족하지 못한다.

음료수를 섞을 때는 원하는 수만큼 자유롭게 섞을 수 있지만, 한 음료수의 일부분만 섞을 수는 없다.

\(N\)과 \(K\) 그리고 각 음료수들의 당분이 정수로 주어질 때, 컴공이가 마실 수 있는 최대 음료수의 부피를 구해보자.

입력

  • 첫 번째 줄에 \(N\), \(K\)가 주어진다.\((1 ≤ N ≤ 10000), (1 ≤ K ≤ 10000)\)
  • 그 다음 줄부터 \(N\)개의 줄에 각 음료수의 당분이 무작위 순서로 주어진다.\((1 ≤ 당분 ≤ 10000)\)

출력

  • 컴공이가 마실 수 있는 최대 음료수의 부피를 출력한다.

입력 예시 1

4 3
1
3
5
1

출력 예시 1

3

입력 예시 2

5 5
4
6
1
3
7

출력 예시 2

4

예시 2 설명

당분이 4, 6, 3, 7인 음료수를 섞으면 총 4의 부피를 마실 수 있다.


Comments

There are no comments at the moment.