[백준 32142] 서바이벌 [Java]

문제

http://boj.ma/32142

요약

• 순서대로 주어지는 학생들의 위치로 다각형을 만들자.
• 거리가 가장 가까운 학생이 여러 명일 경우, 번호가 가장 큰 학생의 위치를 선택하자.

---

풀이 과정

아이디어

순서대로 주어지는 학생들의 위치로 다각형을 구성하되, 거리가 가장 가까운 학생의 위치를 선택해야 합니다.

s(i) → s(i+1)의 거리는 s(i + 1) → s(i + 2)간의 거리보다 작을 때, s(i+1)에서 가까운 거리인 s(i + 2)를 선택함으로써, 단순 다각형 형성을 기대할 수 있습니다.

순서대로 주어지는 학생들의 위치 간 거리는 점점 작아져야 하며 결국 s(n - 1) → s(n)의 거리는 s(n) → s(1)보다 작아지게 됩니다.

이 때 시작 점 s(1)은 역설적으로 s(2)가 아닌, s(n)을 선택하게 되므로 문제 속 조건에서, 단순 다각형은 어떠한 경우에도 형성될 수 없습니다.

System.out.println(-1);

성능 분석

• 시간 복잡도: O(1)
• 제출결과: Accepted / 96ms / 14168KB

---

회고

경기과학고 “나는 코더다 2024 반년대회”의 B번 문제였지만, 예상과 달리 Ad-Hoc 유형이라 처음엔 다소 당황했다. 그래도 문제를 정확히 해석하고, 주어진 조건에서 정답의 근거를 하나씩 찾아 최적의 해에 도달하는 과정은 꽤 흥미로웠다.

이번 경험을 통해 특정 유형에 대한 선입견을 줄이고, 다양한 접근을 시도하는 연습이 필요함을 느꼈다. 앞으로도 Ad-Hoc 문제를 꾸준히 풀며 사고의 유연성을 넓히고 싶다.

---

참고

문제

http://boj.ma/32142

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/32142.java