기록

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 해당 문제는 이분 탐색으로 해결할 수 있다. 1. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 크거나 N과 같다면 랜선의 길이가 속하는 구간 [start, end]를 [(start, end)/2, end]로 줄인다. 2. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 작다면 랜선의 길이가 속하는 구간 [start, end]를 [start, (start, end)/2]로 줄인다. 구간의 크기가 ..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이분 탐색을 이용하여 위의 문제를 해결할 수 있다. 이를 위하여 우선 첫번째 배열을 오름차순으로 정렬해야 한다. 그 뒤에 다음에 따라 특정 수가 존재할 수 있는 짧은 구간[start, end]을 찾는다. 1. [start, end]의 중간 점을 p라고 할때, arr1의 p번째 원소가 찾으려는 값 number보다 크거나 같다면 탐색구간을 [start, p]로 줄인다. 2. arr1의 p번째 원소가 찾으려는..

문제 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 1. 구해야 하는 두 수 중 첫번째 수 a를 선택한다. 2. 지정한 수보다 오른쪽에 있는 수들을 탐색 범위[startPoint, endPoint]로 지정한다. 3. 이분 탐색을 통해 첫번째 수 a와의 합이 0에 가장 가까운 두번째 수 b를 찾는다. 3-1. a+startPoint와 a+endPoint의 곱의 부호가 -이라면 startPoint는 startPoint와 endPoint의 중간이 된다. 3-2. a+startPoint와 a+endPoi..