톱날의 두께
실버 II의견: 0
목공방 장인 도윤은 길이가 제각각인 목재 \(N\)개를 가지고 있다. 주문이 들어와서 길이가 모두 같은 토막 \(K\)개를 만들어야 한다.
그런데 톱으로 목재를 한 번 자를 때마다 톱날의 두께 \(W\)만큼의 목재가 톱밥이 되어 사라진다. 길이 \(a\)인 목재에서 길이 \(L\)짜리 토막 \(k\)개를 얻으려면 자르는 횟수가 \(k-1\)번 이상 필요하므로 \(k \cdot L + (k-1) \cdot W \le a\) 를 만족해야 한다. 마지막 토막을 얻은 뒤 남는 자투리는 버린다.
토막 \(K\)개를 만들 수 있는 토막 길이 \(L\)의 최댓값을 구하여라. \(L\)은 양의 정수이다.
- \(1 \le N \le 100\,000\)
- \(1 \le K \le 10^{18}\)
- \(0 \le W \le 1\,000\)
- \(1 \le a_i \le 10^9\)
- 길이 \(1\)인 토막 \(K\)개를 만들 수 있는 입력만 주어진다.
첫째 줄에 목재의 개수 \(N\), 필요한 토막의 개수 \(K\), 톱날의 두께 \(W\)가 공백으로 구분되어 주어진다.
둘째 줄에 목재의 길이 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
만들 수 있는 토막 길이의 최댓값을 출력한다.
2 4 1
10 7
3
길이 \(3\)으로 자르면 길이 \(10\)짜리에서 \(2\)도막(\(2 \cdot 3 + 1 \cdot 1 = 7 \le 10\)), 길이 \(7\)짜리에서 \(2\)도막을 얻어 총 \(4\)도막이 된다. 길이 \(4\)로는 \(2 + 1 = 3\)도막밖에 얻지 못한다.
2 4 0
8 8
4
톱날 두께가 \(0\)이면 손실이 없으므로 고전적인 자르기와 같다. 길이 \(4\)로 자르면 각 목재에서 \(2\)도막씩 총 \(4\)도막이 나온다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
톱날의 두께
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
톱날의 두께