리본 자르기
실버 III의견: 0
\(K\)개의 리본이 있고, 각 리본의 길이는 정수로 주어진다. 이 리본들을 잘라 길이가 똑같은 조각을 \(N\)개 만들려고 한다.
리본은 양의 정수 길이 \(P\)로 자를 수 있으며, 길이가 \(L\)인 리본에서는 길이 \(P\)짜리 조각을 \(\lfloor L / P \rfloor\)개 얻을 수 있다. (서로 다른 리본을 이어 붙일 수는 없다.)
길이가 똑같은 조각을 \(N\)개 이상 만들 수 있는 조각 길이 \(P\)의 최댓값을 구하시오.
- \(1 \le K \le 10\,000\)
- \(1 \le N \le 1\,000\,000\)
- 각 리본의 길이는 \(1\) 이상 \(2^{31}-1\) 이하의 정수이다.
- 조각을 \(N\)개 이상 만들 수 있음이 보장된다(모든 리본 길이의 합이 \(N\) 이상이다).
첫째 줄에 리본의 개수 \(K\)와 만들어야 하는 조각의 개수 \(N\)이 주어진다.
다음 \(K\)개의 줄에 각 리본의 길이가 한 줄에 하나씩 주어진다.
길이가 똑같은 조각을 \(N\)개 이상 만들 수 있는 조각 길이의 최댓값을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(1 \le K, N \le 1\,000\)이며, 모든 리본의 길이가 \(1\,000\) 이하이다. |
Subtask 2 | 60점 | 추가 제한이 없다. |
4 11
802
743
457
539200길이 \(200\)으로 자르면 \(4 + 3 + 2 + 2 = 11\)개의 조각을 얻어 \(11\)개를 만들 수 있다. 길이 \(201\)로 자르면 \(3 + 3 + 2 + 2 = 10\)개뿐이라 부족하다.
3 4
10
5
65길이 \(5\)로 자르면 \(2 + 1 + 1 = 4\)개를 만들 수 있다. 길이 \(6\)으로 자르면 \(1 + 0 + 1 = 2\)개뿐이다.
rip 작성
출처 지정되지 않음
평가 및 의견
리본 자르기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
리본 자르기