기록

문제 설명url : https://school.programmers.co.kr/learn/courses/30/lessons/43236출발지점과 도착지점 사이에 바위들이 놓여 있다. 바위는 특정 위치에 존재하며, 이 중 n개를 제거할 수 있다. 이때 출발, 바위, 도착 사이의 거리 중 최솟값을 최대화하는 것이 목표이다.예를 들어 다음과 같은 입력이 주어진다:distance = 25rocks = [2, 14, 11, 21, 17]n = 2도착지점까지의 총 거리: 25바위는 위 위치에 존재바위 2개를 제거할 수 있음우리는 바위 사이의 거리 중 최솟값이 가장 크도록 바위를 제거해야 한다.핵심 아이디어이 문제는 다음 질문으로 바꿔 생각할 수 있다:어떤 최소 거리 x가 주어졌을 때, 그 거리 이상을 유지하기 위해 ..

문제 설명url : https://school.programmers.co.kr/learn/courses/30/lessons/43238n: 심사를 받아야 하는 사람 수이다.times: 각 심사관이 한 사람을 처리하는 데 걸리는 시간 목록이다. 모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구하는 것이 목표이다.핵심 아이디어어떤 시간 t가 주어졌을 때, 그 시간 동안 각 심사관이 처리할 수 있는 사람 수는 t // time으로 계산할 수 있다. 모든 심사관의 처리 가능 인원을 더하면, t분 동안 총 몇 명을 처리할 수 있는지 알 수 있다.total = sum(t // time for time in times)이제 이 값을 기준으로 시간 t를 이분 탐색하며, n명 이상을 처리할 수 있는 가장 작은 t를 찾..

문제 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..