마법사의 마법봉
실버 V의견: 0
왕국의 마법사 길드에서 신입 마법사들에게 마법봉을 나누어 주려 한다. 창고에는 길이가 서로 다를 수 있는 마법봉 원재료 \(N\)개가 있다. 마법봉은 정수 길이여야 하므로, 원재료를 정수 길이 \(L\)로 잘라 마법봉을 만든다. 한 원재료에서 길이 \(L\)짜리 마법봉은 \(\lfloor \text{원재료 길이} / L \rfloor\)개 만들 수 있으며, 남은 조각은 버린다.
신입 마법사가 \(K\)명이므로 마법봉을 적어도 \(K\)개 만들 수 있어야 한다. 마법봉의 길이 \(L\)을 가능한 한 길게 만들고 싶다. 조건을 만족하는 최대 정수 길이 \(L\)을 구하여라. (\(L \ge 1\)인 정수이며, 항상 답이 존재함이 보장된다.)
- \(1 \le N \le 200\,000\)
- \(1 \le K \le 10^{14}\)
- 각 원재료의 길이는 \(1\) 이상 \(10^9\) 이하의 정수이다.
- 길이 \(1\)짜리 마법봉은 항상 \(K\)개 이상 만들 수 있음이 보장된다.
첫째 줄에 원재료의 수 \(N\)과 신입 마법사의 수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 원재료의 길이 \(N\)개가 공백으로 구분되어 주어진다.
조건을 만족하는 최대 정수 길이 \(L\)을 출력한다.
3 3
10 7 4
5
길이 \(3\)으로 자르면 \(10 \div 3 = 3\)개, \(7 \div 3 = 2\)개, \(4 \div 3 = 1\)개로 총 \(6\)개 \(\ge 3\)이다. 길이 \(4\)로 자르면 \(2 + 1 + 1 = 4\)개, 길이 \(5\)로 자르면 \(2 + 1 + 0 = 3\)개 \(\ge 3\)이다. 길이 \(6\)로 자르면 \(1 + 1 + 0 = 2\)개 \(< 3\)이므로 답은 \(5\)이다.
5 7
1 2 3 4 5
1
길이 \(1\)로 자르면 총 \(1+2+3+4+5=15\)개, 길이 \(2\)로 자르면 \(0+1+1+2+2=6\)개 \(< 7\), 따라서 답은 \(1\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법사의 마법봉
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법사의 마법봉