[BOJ]3090번: 차이를 최소로

 

www.acmicpc.net/problem/3090

---

jaimemin님의 (jaimemin.tistory.com/987)풀이를 통해 해결하였습니다. 

 

우선 N제한이 크므로 Parametric Search로 해결해야 하는 문제임을 알 수 있습니다.

 

문제 풀이 방법은 다음과 같습니다.

 

배열 내 원소 값 차이의 상한과 하한을 구합니다. 하한(== 0), 상한(== 10^9)

 

mid = (하한 + 상한) / 2인 mid값을 대상으로 질의를 던집니다.

 

"배열 내 모든 원소 값의 차이가 mid 이하로 만드는 것이 T번 변경안에 가능한가?"

 

1. 가능 => mid 더 줄여보기

2. 불가능 => mid 늘려보기

 

isPossible 함수에서 양방향 탐색을 하는 이유는 오직 좌변이 우변보다 큰 경우에만 if문이 돌기 때문입니다.

 

그래서 아래 4가지 경우를 모두 잡아내기 위해 isPossible함수에서 양방향으로 탐색을 합니다.

 

 

arr[i+1] < arr[i] 인 경우,

arr[i+1] > arr[i] 인 경우,

arr[i-1] < arr[i] 인 경우,

arr[i-1] > arr[i] 인 경우,

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ3090.cc