06. 결정 문제

[1. 문제 설명]

N개의 도시를 지나치는데,

i 번째 도시까지의 남은 거리를 나타내는 표지판이

도착하기 M 미터 전부터 시작해서 G 미터 간격으로 설치 된다.

시작점으로 부터 각 도시 까지의 거리(L) 와 M, G 에 대한 값이 주어질 때,

K번째 표지판의 위치를 찾는다.

Li, Mi, Gi (1 <= Gi <= Mi <= Li <= 8,030,000)

[2. 풀이 접근]

decision(x) = 시작점부터 x 미터 지점까지 가면서 K 개 이상의 표지판을 만날 수 있는가?

여기서 x 에 대해서 이분 탐색을 해봐야 한다.

K 에 초점을 맞추는 것이 아니라

어디까지 갔을 때, 몇개의 표지판을 만나는지 확인하는 것.

i 번째 도시에 대한 표지판은

[Li-Mi, Li] 구간내에 존재

x 를 적절히 선택했을 때

[0, x] 와 겹치는 구간의 길이

min(x, L) - (L - M)

# 아래 그림에서 초록색 구간 혹은 빨간색 구간

겹치는 구간의 길이가 0이어도, 하나의 표지판을 보게 된다.

=> (최초 i번째 도시에 대한 표지판)

겹치는 구간의 길이를 G 로 나누고 1을 더하면

i 번째 도시까지의 거리를 나타내는 표지판을 몇개 보는지 알 수 있다.

=> (겹치는 구간의 길이가 0 이어도 하나는 보게되니까)

-1 미터는 하나도 보지못하는 경우

고속도로 끝까지 가면 항상 K개 이상의 표지판을 보게 된다.

[3. 코드]

test_kernelv2