BOJ 18324 - Race

BOJ 18324 - Race

이 문제는 이분 탐색 없이도 수학으로 풀 수 있지만, 이분 탐색을 쓰면 여전히 수학으로 풀 수 있다(?)

그리디하게 따졌을 때 속도는 계속 $(U)+(\rightarrow)*(D)*$ 처럼 진행된다.

올라가는건 1번 이상 하고 유지하는걸 0번이상 내려가는걸 0번 이상 한다.

이때 최대로 올라가는 높이 $M$ 을 이분 탐색으로 찾고, 적절히 수학적 계산을 해주어서 정답을 구하면 된다.

/*  
 * 1. 정수 시간에 달리기를 마친다  
 * 2. K 길이를 달린다.  
 * 3. 도착 지점에서 X 초과의 속력을 가지지 않는다.  
 */  
void solve() {  
   int K, N, X;  
   cin >> K >> N;  
   for (int i = 0; i < N; i++) {  
      cin >> X;  
      // 베시가 처음에 계속해서 속도를 올릴 때  
      // 최대로 올릴 수 있는 속도      int L = 1, R = 1e9, S = -1, Ans = 2e15;  
      while (L <= R) {  
         int M = L + (R - L) / 2;  
         int dist = M * (M + 1) / 2;  
         if (dist > K) {  
            R = M - 1;  
            continue;  
         }  
         // 남은 거리  
         int remain_dist = K - dist;  
         int need_time = max(0ll, M - X);  
         // X 까지 줄이는데 필요한 거리  
         int dist_for_dec = M <= X ? 0 : (M + X - 1) * (M - X) / 2;  
         if (dist_for_dec > remain_dist) {  
            R = M - 1;  
         } else {  
            S = M;  
            L = M + 1;  
            if ((K - dist - dist_for_dec) % M == 0) {  
               Ans = min(Ans, M + need_time + (K - dist - dist_for_dec) / M);  
            } else {  
               Ans = min(Ans, M + need_time + (K - dist - dist_for_dec) / M + 1);  
            }  
         }  
      }  
      cout << Ans << endl;  
   }  
}