SWEA 11592. 크루즈 컨트롤

도로에 말이 달리고 있을 때 목적지까지 말을 추월하지 않고, 속도를 줄이지 않은 상태로 달릴 수 있는 최대 속도를 구하는 문제이다. 사람은 0부터 시작하며 말을 추월할 수 없고, 말은 1마리 혹은 2마리 이며 말의 시작 위치, 속도가 주어지고 말 끼리는 추월할 수 있다.

 

말이 1마리인 경우 말이 종점에 닫는 시간이 걸리는 시간이다. 2마리인 종점에 가까운 말이 먼 말보다 느린 경우 종점에 도착하기 전에 추월당하면 종점에 가까운 말이 종점에 닫는 시간 만큼 걸린다. 종점에 도착후에 추월당한다면 종점 도착 전까지는 종점에 먼 말을 계속 따라가야 하므로 종점에 먼 말이 종점에 도착하는 시간 만큼 걸린다. 종점에서 먼 말이 속도가 느리거나 같아도 종점에서 먼 말이 종점에 도착하는데 필요한 시간 만큼 걸린다. 거리를 시간으로 나누면 속도를 구할 수 있게 된다.

static class Horse implements Comparable<Horse> {
    int start, speed;
        
    public Horse(int start, int speed) {
        this.start = start;
        this.speed = speed;
    }

    @Override
    public int compareTo(Horse o) {
        return o.start - this.start;
    }
}

Horse[] board = new Horse[n];
double min = d * 60 * 60;
for(int i=0; i<n; i++) {
    st = new StringTokenizer(br.readLine());
    int k = Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
    board[i] = new Horse(k, s);
}
Arrays.sort(board);
if(n == 1) min = Math.min(min, (d-board[0].start)/board[0].speed);
else {
    if(board[1].speed > board[0].speed) {
        double sameTime = (double)(board[0].start - board[1].start) / (board[1].speed - board[0].speed);
        if(sameTime * board[1].speed + board[1].start < d) min = Math.min(min, (d-board[0].start)/board[0].speed); 
        else min = Math.min(min, (d-board[1].start)/board[1].speed);
    } else min = Math.min(min, (d-board[1].start)/board[1].speed);
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            double d = Double.parseDouble(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            Horse[] board = new Horse[n];
            double min = d * 60 * 60;
            for(int i=0; i<n; i++) {
                st = new StringTokenizer(br.readLine());
                int k = Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
                board[i] = new Horse(k, s);
            }
            Arrays.sort(board);
            if(n == 1) min = Math.min(min, (d-board[0].start)/board[0].speed);
            else {
                if(board[1].speed > board[0].speed) {
                    double sameTime = (double)(board[0].start - board[1].start) / (board[1].speed - board[0].speed);
                    if(sameTime * board[1].speed + board[1].start < d) min = Math.min(min, (d-board[0].start)/board[0].speed); 
                    else min = Math.min(min, (d-board[1].start)/board[1].speed);
                } else min = Math.min(min, (d-board[1].start)/board[1].speed);
            }
            
            sb.append(d/min).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    static class Horse implements Comparable<Horse> {
        int start, speed;
        
        public Horse(int start, int speed) {
            this.start = start;
            this.speed = speed;
        }

        @Override
        public int compareTo(Horse o) {
            return o.start - this.start;
        }
    }
}