매개 변수 탐색

[BOJ/JAVA] 27313번: 효율적인 애니메이션 감상

27313번: 효율적인 애니메이션 감상 https://www.acmicpc.net/problem/27313 키워드 애니메이션을 최대 M M M시간 동안만 보기로 했다. 한별이는 애니메이션을 동시에 최대 K K K개씩 묶어서 보기로 했는데, 한별이가 동시에 애니메이션을 보는 방법은 다음과 같다. 애니메이션을 보고 있지 않은 상태에서, 한별이는 아직 보지 않은 애니메이션 중 K K K개 이하의 애니메이션을 동시에 보기 시작한다. 애니메이션을 보고 있는 도중에는 새로운 애니메이션을 보기 시작할 수 없다. 이로 인해, 한별이는 보기 시작한 애니메이션 중에서 가장 긴 애니메이션이 끝날 때까지 다른 애니메이션을 보기 시작할 수 없다. 한별이는 애니메이션 시청의 달인이기 때문에 애니메이션이 끝남과 동시에 새로운 애니..

[BOJ/JAVA] 6209번: 제자리 멀리뛰기

6209번: 제자리 멀리뛰기https://www.acmicpc.net/problem/6209키워드돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.구현매개변수 탐색을 이용하여 구현한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 돌섬으로부터 탈출구 까지의 최대 거리(1_000_000_000) 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;m개를 제거했을 때, 거리가 mid 이상이 되도록 할 수 있는가? mid 길이로 나눠줄 수 있다면low = mid + 1 ..

[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장https://www.acmicpc.net/problem/15810키워드풍선을 담당하는 N명의 스태프대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰각 스태프가 풍선 하나를 만드는 시간(분) A_i를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?구현매개변수 탐색을 이용하여 구현한다.범위가 int 범위를 초과하므로 long 자료형을 이용한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;mid 시간내로 만들 수 있는지 체크한다. mid 시간 내로 만들 수 있다면high = ..

[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기https://www.acmicpc.net/problem/16401키워드반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.구현나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자. 매개변수 탐색을 이용하여 구현한다. 템플릿low, high 값은 항상 범위 내로 설정한다.low = 0high = 길이가 가장 긴 과자 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2..

[BOJ/JAVA] 2110번: 공유기 설치

2110번: 공유기 설치도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.https://www.acmicpc.net/problem/2110키워드집에 공유기 C개를 설치가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치구현huses[] 각 집의 좌표를 오름차순으로 정렬한다.solution()인접한 두 공유기 사이의 거리를 매개변수로 이분탐색을 진행한다.초기 low는 1초기 high는 마지막원소 - 첫번째 원소 (이 때가 차이가 가장 크므로..)[low, high]에 속하면서, mid = (lo..

[BOJ/JAVA] 2343번: 기타 레슨

키워드블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.M개의 블루레이에 모든 기타 강의 동영상을 녹화하블루레이의 크기(녹화 가능한 길이)를 최소M개의 블루레이는 모두 같은 크기구현블루레이 크기를 매개변수로하여 이분 탐색을 진행한다.lectures[]강의의 누적합low = 가장 긴 길이의 강의high = 모든 강의 길이의 합canMake()mid = (low+high)/2 의 블루레이 크기로 녹화할 수 있는지 체크0부터 누적합을 계산하며 진행한다. mid보다 커지는 순간 → 현재 인덱스의 강의를 제외한 이전 강의를 현재 블루레이에 담는다.마지막 인덱스가 아닌데, 블루레이의 수가 M이상이라면 .. false 반환반복문이 끝난 경우 → 디스크가 남는 경우디스크의 크기는 항상 한 개의 강의를 넣을만큼 충분..

[BOJ/JAVA] 23631번: 진심 좌우 반복뛰기

키워드위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.정확히 (N - 1)m만 뛸 것구현다음을 정의하자. 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.n전부 뛴 횟수전부 뛸 수 있는 n값을 구한다.low = 0high = 5000(5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.n을 매개변수로 하여, 이분 탐색으로 진행한다.숫자가 매우 크므로, java에서는 BigInteger를 활용한다.n번째에서 전부 뛰었을 때 위치는 다음과 같다.이동 횟수좌표1K2-K32K4-2K53K6-4K위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 ..