백준 19592 - 장난감 경주 (자바 - 이분 탐색)

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

19592번: 장난감 경주

 

* 문제 요약

당신을 포함한 N명의 참가자가 각자 자신의 장난감 자동차를 이용해 경주를 하는데, 트랙의 길이는 X 미터이다.

참가자는 1번 부터 N번까지 번호가 매겨져 있고, 당신의 참가 번호는 N번이다.

i번 참가자의 자동차의 일반적인 속도는 V[i] m/s 이며, 당신을 제외한 모든 참가자의 자동차는 출발점 부터 도착점까지 항상 일정한 속도로 움직인다.

단, 당신의 장난감 자동차는 특수 부스터가 있기 때문에, 처음 1초간 Z m/s 로 움직이도록 설정할 수 있다.

(이 때, 트랙의 나머지 거리는 V[N] m/s 로 일정한 속도로 움직인다.) 경주 시작 전 정수 Z값을 고를 수 있으며, 이 값은 반드시 부스터 속도 한계치인 Y m/s 이하이어야 한다. (Z <= Y)

당신은 꼭 이 경주에서 단독 1등을 하고 싶은데, 부스터를 지나치게 사용하면 의심 받을 수 있으니 단독 우승이 가능토록 하는 최소의 Z값을 구하고 싶다.

 

예를 들어 N = 3, X = 12, Y = 11 이라하고, V = [3, 2, 1] 이라 하자.

- 1번 참가자의 자동차는 3 m/s 의 일정한 속도로 움직여서 4초만에 경주를 마친다.

- 2번 참가자의 자동차는 2 m/s 의 일정한 속도로 움직여서 6초만에 경주를 마친다.

- 3번 참가자인 당신의 경우 여러가지 가능성이 있다.

  - 부스터를 사용하지 않으면 1 m/s 의 일정한 속도로 움직여서 12초만에 경주를 마친다.

  - 부스터를 최대치로 사용하면 (Z = Y) 첫 1초간 11m 를 이동하고, 나머지 1m 를 1초간 주행해서 2초만에 경주를 마치며 단독 우승을 할 수 있다.

  - 부스터를 조금 덜 사용하여 Z = 10 미터를 1초만에 이동하면, 나머지 2m 는 원래 속도로 이동하여 총 3초가 걸리고, 단독 우승할 수 있다.

  - 그보다 조금 덜 사용하여 Z = 9 미터를 1초만에 이동하면, 나머지 3m 는 원래 속도로 이동하여 총 4초가 걸리고, 1번 자동차와 같은 시간만큼 걸린다. (공동 우승)

 

위의 예제의 경우 단독 우승을 하기 위해 최소 10미터를 부스터를 사용하여 이동하여야 하므로 원하는 답은 10이다.

입력으로 N, X, Y, 그리고 각 장난감 자동차의 속도 V가 주어졌을 때, 단독 우승을 하기 위해 부스터를 사용해서 이동해야 하는 최소한의 거리를 구하는 프로그램을 작성하시오.

 

* 입력

첫 줄에 테스트 케이스의 수 T 가 주어진다. 

각 테스트 케이스의 첫 줄에 N, X, Y 가 공백으로 주어진다.

둘째 줄에 N개의 정수가 공백으로 구분되어 주어지는데, 이는 각 장난감 자동차의 속도 V[i] 를 나타낸다.

 

* 출력

각 테스트 케이스에 대해 단독 우승을 위해 부스터를 사용해서 이동해야 하는 최소한의 거리를 출력한다.

만약 부스터를 쓰지 않고도 단독 우승이 가능하다면 0 을 출력한다.

부스터를 최대치로 사용하고도 단독 우승이 불가능하다면 -1 을 출력한다.

 

* 제한

- 1 <= T <= 10

- 2 <= N <= 1,000

- 1 <= Y <= X <= 1,000,000

- 1 <= V[i] <= 1,000,000

 

* 예시

 

* 해결 과정

모든 참가자들 중 자기 자신의 참가번호는 항상 맨 마지막이기 때문에, 자신을 제외한 다른 모든 참가자들이 트랙을 완주하는 시간 중에서 최소 시간을 구해준다.

다른 참가자들의 완주 시간 중 최소 시간을 구할 때, 각 참가자의 자동차 속력이 트랙의 길이와 정확히 나누어 떨어지지 않을 수 있으므로 소수점 계산을 위해 트랙의 길이 x 와 해당 참가자의 속도 v[i] 를 나누어서 구한 몫에 1.0 을 곱해주자.

(이 포인트를 빨리 잡지 못해서 문제를 푸는데 시간이 좀 걸렸다.)

 

이후 아래와 같이 조건문을 처리해주자.

1. 부스터를 쓰지 않고도 단독 우승할 수 있는 경우. 즉, 다른 참가자들의 트랙 완주 시간중 최소 시간보다 본인의 트랙 완주시간이 더 빠른경우 (min > 1.o * x / v[n-1])

2. 최소한의 부스터를 사용하기는 해야 우승을 할 수 있는 경우

- 다음과 같이 이분 탐색을 수행한다.

  - start = 0, end = y 두 가지 변수를 선언해 매 반복마다 부스터 속도를 mid = (start + end) / 2 값으로 특정해서 단독 우승이 가능한지 살펴본다.

  mid 값 만큼 부스터를 밟았을 때 단독 우승이 가능할 경우, 단독 우승이 가능한 최소한의 부스터 속도를 찾기 위해 end 값을 mid - 1 만큼 줄인다.

  - mid 값 만큼 부스터를 밟았을 때 단독 우승이 불가능한 경우 start 를 mid + 1 만큼 늘려준다.

 

더 이상 조건을 만족하지 않아 (start  <= end) 반복문이 끝나고 난 후 다음과 같은 조건에 따라 답을 출력해준다.

1. start 가 y 보다 큰 경우. 즉, 부스터 최대 제한 속도인 y를 사용해도 단독 우승이 불가능해 결국 반복문 도중에 start 값이 y 를 넘어가 버린 경우 -1 을 출력해준다.

2. 그렇지 않을 경우 start 값을 출력해준다. (단독 우승이 가능한 부스터 최소 속력을 출력해줘야 하기 때문)

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());

        for (int i = 0; i < tc; i++) {
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int x = Integer.parseInt(input[1]);
            int y = Integer.parseInt(input[2]);

            int vArray[] = new int[n];
            input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                vArray[j] = Integer.parseInt(input[j]);
            }

            // 마지막 주자를 제외한 다른 사람들의 완주 시간 중 최소값을 구한다.
            double min = Double.MAX_VALUE;
            for (int j = 0; j < n - 1; j++) {
                // 트랙의 길이와 자동차의 속력이 정확히 나누어 떨어지지 않을때
                // 소수점 계산을 위한 1.0 곱셈
                min = Math.min(min, 1.0 * x / vArray[j]);
            }

            // 부스터를 쓰지 않고도 단독 우승을 할 수 있는 경우
            if (min > 1.0 * x / vArray[n - 1]) {
                bw.write(0 + "\n");
            } else {
                // 부스터를 최대로 사용했을 때 단독 우승이 가능한 경우
                int start = 0;
                int end = y;

                while (start <= end) {
                    int mid = (start + end) / 2;

                    // mid 만큼 부스터를 밟았을 때 단독우승이 가능할 경우 end 를 줄임
                    if (min > ((1.0 * x - mid) / vArray[n - 1]) + 1) {
                        end = mid - 1;
                    }
                    // mid 만큼 부스터를 밟았을 때 단독 우승이 불가능한 경우 start 를 늘림
                    else {
                        start = mid + 1;
                    }
                }

                // 부스터를 최대 이상으로 올려야 단독 우승이 가능한 경우
                if (start > y) {
                    bw.write(-1 + "\n");
                } else {
                    bw.write(start + "\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

부스터 사용 범위를 최소, 최대로 나눈 뒤 중간에 있는 값을 특정해서 단독 우승 여부에 따라 범위를 줄여가며 단독 우승이 가능한 최소 속력을 찾았으므로 이분 탐색 문제에 해당된다.