1. 출제자가 의도한 풀이는 이분매칭
2. 이 문제를 보고 감이 안와서 질문들을 보고 해결
3. min, max 범위를 계속 구하고
4. 마지막에 min > max + 앱실론 으로 확인
5. 실수 연산에는 앱실론을 앞으로 거의 계속 사용하자.
import java.util.*; | |
import java.io.*; | |
/** | |
* https://www.acmicpc.net/problem/14488 | |
* BOJ 백준온라인져지 14488 준오는 급식충이야!! 풀이 | |
*/ | |
public class Main { | |
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
public static void main (String args[]) throws IOException { | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
String str1[] = br.readLine().split(" "); | |
int N = Integer.parseInt(str1[0]); | |
double T = Double.parseDouble(str1[1]); | |
long position[] = new long[N]; | |
String str2[] = br.readLine().split(" "); | |
for (int i = 0; i < N; i++) { | |
position[i] = Long.parseLong(str2[i]); | |
} | |
double min = -1000000000 * 1200000000; | |
double max = 1000000000 * 1200000000; | |
String str3[] = br.readLine().split(" "); | |
for (int i = 0; i < N; i++) { | |
int velocity = Integer.parseInt(str3[i]); | |
min = Math.max(min, velocity * -T + position[i]); | |
max = Math.min(max, velocity * T + position[i]); | |
} | |
if (min > max + 1e-04) bw.write("0"); | |
else bw.write("1"); | |
bw.flush(); | |
} | |
} |
문제
심술쟁이 해커 임준오(동탄 주민)는 오늘도 점심시간을 기다리고 있다. 준오와 친구들은 매일 복도 어딘가의 한 지점에 모여서 함께 밥을 먹으러 간다. 선린의 복도는 직선형으로 되어있고, 준오와 친구들은 이 복도 어딘가에 위치한 교실에서 종이 치기만을 기다리고 있다.
‘띵~ 디딩~ 띵디딩디딩~’
종이 울렸다! 준오와 친구들은 최대한 빨리 한 지점에서 만나야한다. 그렇지 않으면 홍수처럼 쏟아지는 학생들에 휩쓸려 제각각 급식실로 떠내려갈지도 모른다.
준오를 포함한 친구들의 교실 위치 xi와 각 학생들의 달리기 속도 vi, 그리고 홍수가 밀려오기까지 남은 시간 T가 주어진다. 과연 준오와 친구들은 함께 밥을 먹으러 갈 수 있을까?
교실은 1차원 직선 위 어딘가에 위치해있다. 학생들의 달리기 속도는 항상 일정하며, 모든 학생들이 종이 울림과 동시에 뛰어나온다. 홍수가 터지는 시점과 친구들이 만나는 시점이 일치한다면 홍수에 떠내려가기 전에 만날 수 있는 것으로 간주한다.
입력
첫째 줄에는 준오를 포함한 친구들의 수 N과 홍수까지 남은 시간 T가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ T(초) ≤ 1,000,000,000) 남은 시간 T는 소숫점 넷째자리의 실수로 주어진다.
둘째 줄에는 N명 학생들의 위치 x1, x2, ..., xn(1 ≤ xi ≤ 1,000,000,000)가 주어진다. (자연수, 미터 단위)
셋째 줄에는 N명 학생들의 속도 v1, v2, ..., vn(1 ≤ vi ≤ 1,000,000,000)가 주어진다. (자연수, 초당 미터)
출력
준오와 친구들이 모두 만날 수 있으면 1을, 그렇지 않으면 0을 출력한다.
'IT > 알고리즘' 카테고리의 다른 글
BOJ 백준온라인져지 2635 수 이어가기 풀이 (0) | 2018.04.19 |
---|---|
BOJ 백준온라인져지 6986 절사평균 풀이 (0) | 2018.04.18 |
BOJ 백준온라인져지 5347 LCM 풀이 (0) | 2018.04.16 |
BOJ 백준온라인져지 2532 반도체 설계 풀이 (1) | 2018.04.11 |
BOJ 백준온라인져지 8595 히든 넘버 풀이 (0) | 2018.04.10 |