| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 205 | 88 | 70 | 41.420% |
1차원 평면에 $N$개의 선분이 존재한다. 1차원 평면상의 $x = S$부터 $x = E$까지의 구간을 주어진 선분을 최대 3개 사용하여 모두 덮으려 한다.
시작점이 $x=l$이고 끝점이 $x=r$인 선분이 점 $x$를 덮는다는 것은 $l \leq x \leq r$을 의미하고, 선분 집합 $L$이 $x=S$부터 $x=E$까지를 덮을 수 있다는 것은 $S \leq x \leq E$인 모든 실수 $x$에 대해 $x$를 덮는 선분이 $L$에 적어도 하나 이상 존재함을 의미한다.
이때, 구간을 덮는 방법에 따라 '오차'라는 값을 정의하자.
'오차'는 사용한 선분 중 서로 다른 2개를 골랐을 때 겹치는 구간의 길이의 합이다. 만약 선분 하나로 $x = S$부터 $x = E$까지 모두 덮을 수 있다면 이 방법의 오차는 0이다.
'오차'를 최소화하면서 $x = S$부터 $x = E$까지 최대 3개의 선분을 사용하여 덮어보고, '오차'의 최솟값을 출력하자.
첫 번째 줄에 선분의 개수 $N,ドル 시작점 $S$와 끝점 $E$가 공백으로 구분되어 주어진다.
이후 $N$줄에 걸쳐 그중 $i (1 \leq i \leq N)$번째 줄에 $i$번째 선분의 시작점 $s_i$와 끝점 $e_i$가 공백으로 구분되어 주어진다.
첫째 줄에 가능한 오차의 최솟값을 출력한다.
만약 어떻게 하더라도 $x=S$부터 $x=E$까지 덮을 수 없다면 $-1$을 출력한다.
3 1 10 1 7 2 10 3 6
5
1번, 2번, 3번 선분을 사용하는 경우 1번과 2번은 $x=2$부터 $x=7$까지, 2번과 3번은 $x=3$부터 $x=6$까지, 1번과 3번은 $x=3$부터 $x=6$까지가 겹친다. 따라서 이 경우 오차는 5ドル + 3+ 3 = 11$이다.
1번과 2번 선분을 사용하는 경우 $x=2$부터 $x=7$까지가 겹친다. 따라서 이 경우 오차는 5ドル$이다. 이보다 작은 오차로 $x=1$부터 $x=10$까지를 덮는 방법은 없다.
5 14 46 1 16 32 45 39 48 42 47 36 46
-1
어떤 방법을 쓰더라도 $x=14$부터 $x=46$까지를 모두 덮는 것은 불가능하다.
School > 경기과학고등학교 > IamCoder Qualification Test > 2024 IamCoder Qualification Test D번