백준 14488번: 준오는 급식충이야!!

백준 14488번: 준오는 급식충이야!!

14488번: 준오는 급식충이야!!

 

 

• 각 좌표에서 이동할 수 있는 범위를 구한 뒤, 모든 데이터의 교집합이 있으면 1을 출력하고 교집합이 없으면 0을 출력한다.

- 다음 예제를

3 2.5
1 7 5
2 1 1

을 살펴보자.

• 1에서는 2.5초 동안 [-4, 6] 사이를 이동할 수 있다. 마찬가지로 7과 5에서는 각각 [4.5, 9.5], [2.5, 7.5]사이를 이동할 수 있다. 교집합이 [4.5, 6]으로 존재하므로 이 경우에는 만날 수 있다.
• 따라서 좌표x에 (v*t)를 각각 더하고 빼서 x의 이동 가능 범위를 구한뒤 교집합을 찾으면 된다. 양의 방향으로 움직을 때의 최솟값이 음의 방향으로 움직일 때의 최댓값보다 크거나 같으면 1을 출력하고 그 외의 경우에는 0을 출력하면 된다.

- 그래서 위를 바탕으로 자바 코드를 짜보면 아래와 같다.

import java.util.*;
import java.io.*;

public class Main{
    static int n;
    static double t;
    static double[] x;
    static double[] v;
    static double MIN_RANGE = 1000000001;
    static double MAX_RANGE = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        t = Double.parseDouble(st.nextToken());

        x = new double[n];
        v = new double[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            x[i] = Double.parseDouble(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            v[i] = Double.parseDouble(st.nextToken());

        for (int i = 0; i < n; i++) {
            MIN_RANGE = Math.min(MIN_RANGE, x[i] + v[i] * t);
            MAX_RANGE = Math.max(MAX_RANGE, x[i] - v[i] * t);
        }

        if (MIN_RANGE >= MAX_RANGE)
            System.out.println(1);
        else
            System.out.println(0);
    }
}

※ 언뜻보면 통과할 것 같지만 위 코드는 통과하지 못한다. 왜냐하면 t가 소숫점 아래 4자리의 실수이기 때문이다. double형 실수의 부동소수점 방식 때문에 정확한 비교가 어려워서 오차가 발생하기 때문이다. 따라서 Math.min()과 Math.max()를 사용할 때 Math.round()를 통해서 소숫점 아래 4자리에서 반올림을 한 뒤 비교를 하면 통과할 수 있다. 백준의 질문 게시판의 이 글을 참고하면 도움이 많이 될 것 같다.