71. 백준 : Segments ( 2025 ICPC : Problem L )

 

 

[ 문제 설명 ]

여러 수평 선들이 있다.

그 가운데에 수직선 x=p 를 그었을 때, 각각의 선이 해당 수직선에 닿기 위해서 선을 늘린다고 할 때

늘리는 크기의 최댓값을 구해라.

 

📌 중요한 아이디어

1. 연산에 크게 중요하지 않은 값을 생각해보자.

입력은 (x시작, x끝 , y) 이다. 우리는 y값을 사용하지 않기 때문에 굳이 고려하지 않아도 된다.

선의 연장은 x축으로만 하니까!

 

---

2. 연산에 쓰이는 값을 생각해보자.

위 예시로 보면, {2,5,3 } { 14,17,5 } 의 요소들만 사용된다.

이 안에서도 5랑 14만 사용됨.

 

5는 (x시작, x끝 , y) Pair들을 모두 두고 봤을 때

x끝 값중에 가장 작은 값이다.

 

14는 (x시작, x끝 , y) Pair들에서

x시작 값 중에 가장 큰 값이다.

 

그럼 매 입력을 받을 때,

x시작 값 중 가장 큰 값인지 비교하여 담고

x끝 값 중 가장 작은 값인지 비교하면서 담으면 된다.

 

 

 

처음에는 마지막 max 안에 0을 넣어주지 않아서 WA가 나왔다.

모든 선 안에 포함되는 경우에는 선을 그을 필요가 없기 때문에, 해당 케이스도 고려해주어야 한다.

 

---

ICPC 문제에서 그나마 도전해볼만한 문제를 풀어봤다.

대회에서 팀원이 풀었는데, 그 당시에도 내가 해볼만하다 싶은 문제 중에 하나였다.

어떤 값을 어떻게 가져올지만 판단하는 게 가장 중요한 요소같다.

 

내 기억으로 이거 못 푼 팀은 없었던 것 같은데, 정말 사람들 다 대단한 것 같다.