2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 이진탐색(Binary Search) 문제 구하고자 하는 것 : 두 공유기 사이의 최대거리 lt = 1 rt = arr[n-1] ➜ 너무 세세하게 생각X. 그냥 가장 멀리있는 좌표 선택 ➜ 답(두 공유기의 최대거리)은 lt~rt 사이에 확실하게 있다. mid = (lt + rt ) / 2 가장 인접한 두 공유기의 거리를 mid라고 했을 때, 답이 가능한지 검증 ➜ 공유기의 배치 수를 count하는 함수 생성 ..
💡 이분탐색(Binary Search) 문제 ✅ 구하고자 하는 것 : N개를 만들 수 있는 랜선 최대 길이lt = 1rt = 랜선 길이 중 가장 긴 값 ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다.자를 랜선의 길이가 mid이면 답으로써 가능한 숫자인가 검증 ➜ 얻을 수 있는 랜선의 개수를 구하는 함수 생성얻을 수 있는 랜선의 개수가 N개 보다 크거나 같으면 자를 랜선의 길이를 늘려도 됨 lt=mid+1반대면 랜선의 길이 줄이기 rt=mid-1👨🏻💻 실행코드import java.util.*;import java.io.*;public class Main { private static BufferedReader br = new BufferedReader(new InputStrea..
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡 이진탐색(Binary Search) 이진탐색으로 해결할 수 있는 문제들의 유형은 비슷하다. lt와 rt를 정하고 lt ~ rt 사이에 찾고싶은 답이 분명히 있다라는 확신이 있는 문제에 적용한다 + 최대/최소 구하고자 하는 것 : 절단기를 설정할 수 있는 높이의 최대값 lt = 0 : 절단기에 설정할 수 있는 가장 작은 값 rt : 나무의 길이 중 가장 긴 값 ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다. ..
