Hyun's_Devlog

https://www.acmicpc.net/problem/13397

이분탐색으로 접근했다.

풀이 방법

배열의 크기 N이 최대 5000으로 작은 값에 속한다. 따라서 이분탐색으로 찾게 될 값은 구간의 최대 점수를 찾는 문제로 접근했다.

즉 이분탐색으로 mid값을 고정하고 길이 N의 배열을 순차탐색하면서 탐색 중인 구간의 최댓값 - 최솟값이 mid보다 크다면 구간을 나누어 마지막까지 탐색이 끝났을 때 구간의 개수가 M이하라면 최대 점수를 더 낮은 쪽을 탐색, 개수가 M보다 크다면 최대 점수가 더 큰 쪽으로 이분 탐색을 이어가면 된다.

입력 예제를 기준으로 동작을 그림으로 나타내면 다음과 같다. 이분탐색 mid 값이 3, 5, 4 일 경우 각각의 구간의 개수 조건을 확인. 구간의 최댓값이 5일 경우에 조건을 만족하므로 5가 정답이 된다.

정답 코드

https://www.acmicpc.net/problem/8983

이분탐색으로 접근했다.

풀이 방법

주어지는 사대의 위치를 오름차순으로 정렬한다.

이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.

이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.

해당 방법으로 접근한다면 O(100,000 * log100,000) 즉 O(500,000)에 탐색이 가능하다.

정답 코드

https://www.acmicpc.net/problem/2143

누적합과 이분 탐색을 통해 접근하였다.

풀이

두 배열의 누적합을 통해 부 배열을 생성, 두 개의 부 배열 중 하나의 부 배열을 오름차순 정렬한 뒤 이분 탐색을 수행, (T - 다른 부배열의 원소) 값을 찾아낸다면 해당 값의 개수만큼 정답을 추가하여 마지막에 출력하면 된다.

정답 코드