SY DevLog

8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 이분탐색을 이용하여 해결할 수 있다. 사대의 위치를 arr 배열에 오름차순으로 정렬한다. 정렬 전 : 6 1 4 9 정렬 후 : 1 4 6 9 특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다. 이분탐색을 진행하는 방법은 다음과 같다. arr[middle] == x 이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가..

11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 통나무를 선형으로 배열하는 것이 아니라 원형으로 배열하기 때문에 처음과 끝이 만난다. 그러므로 통나무를 단순히 오름차순, 혹은 내림차순으로 정렬하면 최소 난이도를 구할 수 없다. 예를 들어 오름차순으로 정렬하면 가장 왼쪽에는 최소값, 가장 오른쪽에는 최대값이 배치되는데, 원형이기 때문에 둘 사이의 차이도 난이도에 포함된다. 최대값에서 최소값을 뺀 값은 가장 큰 차가 되므로 최소 난이도를 구할 수 없다. 그래서 최소 난이도를 구하기 위해서는 중간에 위치한 통나무의..