[Kickstart][2020][Round B] 2. Bus Routes

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83bf

---

n개의 버스노선을 이용하여 여행을 하고 싶다.
버스노선을 차례대로 이용한다고 했을 때 (i < j, Xi 이용 후 Xj 이용) D 일 이내에 여행을 마쳐야 한다(마지막 버스를 D일 이내에 타야한다).

i번 노선의 배차 간격이 주어졌을 때, (예를 들어 Xi = 2라면, i번째 버스는 2, 4, 6 ... 에 이용 가능하다.) 하루에 여러개의 버스 노선의 이용이 가능하다고 한다.

가능한 늦게 여행을 시작하고 싶을 때, D일 이내에 도착할 수 있는 여행 시작일을 구하라. D일까지 여행을 마치는 것이 가능하다.

(버스 노선을 차례대로 이용할 때, D일 이내에 여행을 마칠 수 있는 경우들 중 여행 시작일이 가장 늦은 날 구하기) 

---

이분탐색으로 정답 가능범위를 0~D일에서 좁혀나간다.

정답 가능범위의 가운데(m)를 시작일로 잡고 여행을 시작했을 때, D일 이내에 여행을 마칠 수 있는지 확인한다.

확인 방법은 버스 노선을 처음부터 끝까지 탐색하면서 현재 날짜에서 탐색중인 버스노선을 탈 수 있는 최단 일을 구하면서 날짜를 갱신해나간다. 버스노선을 탈 수 있는 최단 일은 현재 날짜를 day, 탐색중인 버스노선의 배차간격이 routes[i]라 했을 때,

day가 routes[i]로 나누어 떨어졌을 때는, day이고(ex, day = 6, routes[i] = 3 -> 최단일 = 6). 나누어떨어지지 않았을 때는 day + routes[i] - (day % routes[i]) 이다. day % routes[i]는 day를 routes[i]로 나누었을 때 남은 날짜이다. 우리는 i 번 노선을 타기 위해서는 day 이상의 날짜들 중 routes[i]로 나누어 떨어지는 수를 구해야된다. 따라서 남은 날짜를 매꿔야 하므로 routes[i] - (day % routes[i])를 현재 날짜에 더해줌으로서 나누어 떨어지는 수를 구한다.

(ex, day = 6, routes[i] = 5 ->

day % routes[i] = 1.

routes[i] - (day % routes[i]) = 4.

day + routes[i] - (day % routes[i]) = 10.)

모든 노선을 탐색했을 때, 현재 날짜가 D보다 작거나 같으면 정답이 가능한 경우이고 D보다 크면 불가능한 경우이다. 

여행 시작일이 가장 늦은 날(큰 값)을 구해야 하기 때문에, 정답이 가능한 경우 왼쪽 범위를 m으로 갱신하고 불가능한 경우 오른쪽 범위를 m-1로 갱신한다. 이 때, 왼쪽 범위는 이미 탐색한 m으로 갱신되기 때문에 탐색한 수를 다시 탐색하지 않기 위해 가운데(m)를 구할 때 (왼쪽 + 오른쪽 + 1 / 2 ) 로 구해야한다.

왼쪽 범위가 오른쪽 범위 보다 크거나 같아지기 전까지 위 과정을 반복한다. 크거나 같아진 경우 왼쪽 범위가 정답이 된다.

 

M = D, N = n이라 했을 때, 시간복잡도는 정답 가능 범위 구하는 시간 O(logM). 모든 버스노선을 방문했을 때 최종일을 구하는데 드는 시간 O(N)이므로 총 O(NlogM)이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundB/2.%20Bus%20Routes.cpp