백준 1654. 랜선 자르기
조건
K개 랜선들을 같은 길이를 가진 N개의 랜선으로 절단
항상 자연수 길이로 잘리고
N개 초과도 N개 만든걸로 침
N개로 자르는 최대 길이 구하기
K ≦ N, 1<= K <= 10000, 1<= N <= 1000000
각 랜선의 길이는 int의 최대값 2^31 - 1 이하 자연수
생각
일단 입력된 랜선들의 길이를 쭉 저장해놓고
자르는 기준을 잡고 이분 탐색을 해 나가면
빠르게 최대 길이를 찾을 수 있을 것
*유의할 것은 이분 탐색의 양 끝값이
탐색도중 int의 범위를 넘어 오버플로 날 수 있으므로
long long이나 unsigned int를 써줘야 정답이 나온다
K개 랜선들을 같은 길이를 가진 N개의 랜선으로 절단
항상 자연수 길이로 잘리고
N개 초과도 N개 만든걸로 침
N개로 자르는 최대 길이 구하기
K ≦ N, 1<= K <= 10000, 1<= N <= 1000000
각 랜선의 길이는 int의 최대값 2^31 - 1 이하 자연수
생각
일단 입력된 랜선들의 길이를 쭉 저장해놓고
자르는 기준을 잡고 이분 탐색을 해 나가면
빠르게 최대 길이를 찾을 수 있을 것
#include <iostream> #include <vector> typedef unsigned int uint; int bs(int k, int n, std::vector<int> &vec) { uint p = 0, q = 0x7FFFFFFF; while (p <= q) { int cnt = 0; uint cut_size = (p + q) / 2; for (int a : vec) cnt += a / cut_size; if (cnt < n) q = cut_size - 1; else p = cut_size + 1; } return q; } int main() { int k, n, t; std::vector<int> vec; scanf("%d %d", &k, &n); for (int i = 0; (i < k) && scanf("%d", &t); ++i) vec.push_back(t); printf("%d", bs(k, n, vec)); }
*유의할 것은 이분 탐색의 양 끝값이
탐색도중 int의 범위를 넘어 오버플로 날 수 있으므로
long long이나 unsigned int를 써줘야 정답이 나온다
