devbelly

문제 www.acmicpc.net/problem/2613 알고리즘 이분탐색 풀이 $N$개의 구슬을 $M$개로 나눌 때, 각 그룹마다의 합이 가장 큰 것이 최소가 되게 하는 문제입니다. 최대의 최소화. 익숙한 이분탐색의 주제입니다. $solve$함수에서 입력값을 기준으로 $M$개 이하의 그룹을 만들 수 있는지 확인합니다. 딱 $M$개가 아닌 이하도 포함을 하는 이유는 그룹을 새로이 쪼개어 $M$개의 그룹을 만들 수 있기 때문입니다. 코드 #include #define rep(i, n) for (int i = 0; i p) { psum = 0; group += 1;..

문제 www.acmicpc.net/problem/18877 알고리즘 binary search 풀이 COWVID-19의 영향으로 사회적 거리두기를 실천하는 소들의 수가 주어집니다. 목초지의 범위가 주어지고 해당 범위안에 소를 배치하되, 가장 가까운 소의 거리가 최대가 되도록 하는 문제입니다. 소들을 임의의 거리 $d$로 배치할 수 있다면, $d$이하의 거리로 소를 배치할 수 있음이 자명합니다. 이분탐색으로 범위를 좁혀나갈 수 있다는 뜻과 동치입니다. $solve$함수는 거리$d$로 $N$마리의 소를 배치할 수 있는가를 리턴하는 함수입니다. $cur$은 가장 최근에 소를 배치한 지역을 의미합니다. 맨 처음에는 당연히 소를 배치하지 않았으므로 가장 작은 수로 초기화를 합니다. 다음의 $cur$이 될 수 있는 ..