[BJ] 19592 장난감 경주

BJ S5 19592 장난감 경주

 

 

문제링크

https://www.acmicpc.net/problem/19592

19592번: 장난감 경주

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ S5 19592 장난감경주 HD 1080p - YouTube

- YouTube

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * 
 * @author 은서파
 * @since 2021/12/03
 * @see https://www.acmicpc.net/problem/19592
 * @performance 수학: 13328 112 이분탐색: 14636 108
 * @category #이분탐색, #수학
 */

public class BJ_S5_19592_장난감경주 {

    private static int N, X, Y, MAX_SPEED, V, Z;
    private static StringBuilder output;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        output = new StringBuilder();

        int T = Integer.parseInt(input.readLine());
        StringTokenizer tokens = null;
        for (int t = 0; t < T; t++) {
            tokens = new StringTokenizer(input.readLine());
            N = Integer.parseInt(tokens.nextToken());
            X = Integer.parseInt(tokens.nextToken());
            Y = Integer.parseInt(tokens.nextToken());

            tokens = new StringTokenizer(input.readLine());
            MAX_SPEED = Integer.MIN_VALUE;
            for (int n = 0; n < N - 1; n++) {
                V = Integer.parseInt(tokens.nextToken());
                MAX_SPEED = Math.max(MAX_SPEED, V);
            }
            // 나의 속도
            V = Integer.parseInt(tokens.nextToken());
            // 입력 완료

            // 경쟁자의 도달 시간
            double competitor = 1.0 * X / MAX_SPEED;

            // 부스트를 안쓰고도 이기면..
            if (V > MAX_SPEED) {
                Z = 0;
            }
            // 부스트를 최대한 써도 안되면..
            else if (1 + 1.0 * (X - Y) / V >= competitor) {
                Z = -1;
            }
            // 나머지는 찾아보자.
            else {
                // 수학적 처리
                //double temp_z = V + X - 1.0 * X * V / MAX_SPEED;
                //Z = (int) temp_z + 1;

                // 이분 탐색
                int l = 0;
                int r = Y;
                int m = 0;

                while (true) {
                    // 범위가 역전되면 그만~~
                    if (l > r) {
                        break;
                    }

                    m = (l + r) / 2;
                    double mt = 1 + 1.0 * (X - m) / V;
                    // 내 시간이 더 크거나 같으면? 부스트 증가!!
                    if (mt >= competitor) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
                Z = l;
            }
            output.append(Z).append('\n');
        }
        System.out.println(output);
    }

    // REMOVE_START
    private static String src = "5\n" +
                                "3 12 11\n" +
                                "3 2 1\n" +
                                "3 12 9\n" +
                                "3 2 1\n" +
                                "3 12 10\n" +
                                "3 4 5\n" +
                                "3 80 80\n" +
                                "80 60 70\n" +
                                "3 80 80\n" +
                                "70 50 60";
    // REMOVE_END
}