길이가 a₁, …, aₙ인 리본 n개가 있다.
모든 조각의 길이가 같은 양의 정수 L이 되도록 리본을 잘라 조각을 k개 이상 만들려 한다.
리본을 이어 붙일 수는 없고, 자르고 남은 부분은 버린다(길이 a인 리본에서는 길이 L인 조각이 a를 L로 나눈 몫만큼 나온다).
만들 수 있는 가장 큰 L을 출력하라.
L = 1로도 k개를 만들 수 없으면 0을 출력한다.
3 4 5 5 5
2
2 7 3 3
0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
L을 1부터 하나씩 늘려 보면 20억 번까지 가요.
L이 커질수록 조각 수는 줄어드니 '조각이 k개 이상인가'는 앞쪽이 참, 뒤쪽이 거짓이라 이분 탐색으로 31번이면 찾아요.
조건을 함수로 넘겨 받는 탐색 함수를 따로 두면 다른 문제에도 그대로 쓸 수 있어요: Python은 함수 이름을 그냥 넘기고, JavaScript·TypeScript는 화살표 함수 (x: number) => boolean, Java IntPredicate와 ok.test(mid), C# Func<int, bool>, C++ std::function<bool(int)>과 람다, C는 함수 포인터 int (*ok)(int), 크레이콘은 함수 이름을 값으로 넘겨 ok(mid)로 불러요.
함정은 넘침이에요.
① 가운데 (lo + hi) / 2: 길이가 int(약 21억)에 들어가도 lo + hi는 40억이 되어 Java·C#·C·C++에서 넘쳐요 — lo + (hi - lo) / 2로 써요.
JavaScript의 (lo + hi) >> 1도 32비트 정수로 바꿔서 똑같이 깨져요(Math.floor를 써요).
Python·크레이콘은 넘치지 않아요.
② 조각 수는 2×10¹³까지 늘어서 long/long long이 필요해요.
끝으로 L = 1로도 모자라면 1이 아니라 0이에요.
def last_true(lo, hi, ok): """lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.""" answer = lo - 1 while lo <= hi: mid = (lo + hi) // 2 if ok(mid): answer = mid lo = mid + 1 else: hi = mid - 1 return answer n, k = map(int, input().split())a = list(map(int, input().split())) def enough(length): return sum(x // length for x in a) >= k print(last_true(1, max(a), enough))// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo, hi, ok) { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length) => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));import { readFileSync } from "node:fs"; // lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo: number, hi: number, ok: (x: number) => boolean): number { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length: number): boolean => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.function.IntPredicate; public class Main { // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int lastTrue(int lo, int hi, IntPredicate ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok.test(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long k = Long.parseLong(st.nextToken()); int[] a = new int[n]; int longest = 0; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); longest = Math.max(longest, a[i]); } IntPredicate enough = length -> { long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; System.out.println(lastTrue(1, longest, enough)); }}using System;using System.Linq; class Program{ // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int LastTrue(int lo, int hi, Func<int, bool> ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } static void Main() { long k = long.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); Func<int, bool> enough = length => a.Sum(x => (long)(x / length)) >= k; Console.WriteLine(LastTrue(1, a.Max(), enough)); }}#include <algorithm>#include <functional>#include <iostream>#include <vector> // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1.int lastTrue(int lo, int hi, const std::function<bool(int)>& ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} int main() { int n; long long k; std::cin >> n >> k; std::vector<int> a(n); for (int& x : a) std::cin >> x; auto enough = [&](int length) { long long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; std::cout << lastTrue(1, *std::max_element(a.begin(), a.end()), enough) << "\n";}#include <stdio.h> static int n;static long long k;static int a[10000]; /* lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. ok는 함수 포인터로 받는다. */static int last_true(int lo, int hi, int (*ok)(int)) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; /* (lo + hi) / 2 는 int를 넘칠 수 있다 */ if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} static int enough(int length) { long long pieces = 0; for (int i = 0; i < n; i++) pieces += a[i] / length; return pieces >= k;} int main(void) { int longest = 0; scanf("%d %lld", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > longest) longest = a[i]; } printf("%d\n", last_true(1, longest, enough)); return 0;}// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.가장큰참(lo, hi, ok){ answer = lo - 1; 동안 (lo <= hi) { mid = 수학.몫(lo + hi, 2); 만약 (ok(mid)) { answer = mid; lo = mid + 1; } 아니면 { hi = mid - 1; } } 돌려주기 answer;} // 길이 length로 자르면 k조각 이상 나오나충분한가(length){ pieces = 0; 각각 (x 에서 a) { pieces += 수학.몫(x, length); } 돌려주기 pieces >= k;} 첫줄 = 콘솔.수들읽기();k = 첫줄[1];a = 콘솔.수들읽기();longest = 0;각각 (x 에서 a){ longest = 수학.큰수(longest, x);}콘솔.쓰기(가장큰참(1, longest, 충분한가));