BOJ 24233

https://www.acmicpc.net/problem/24233

 

코드

http://boj.kr/ec86dd18783840d69865df8ff58bea42

 

shake! 2021 F

 

난이도 : P2

 

Elapse time : 80min

 

처음 이 문제를 봤을 때 든 생각은 2가지였다. 스위핑을 쓰고 싶다는 생각과 #1665와 상황이 비슷 점이 있다는 것이었다. 하지만 물고기가 각자 속도를 가지고 있다는 점과 길이가 제각각이라는 점이 풀이를 떠올리기 힘들게 만들었다. 풀이를 생각하던 중 물고기의 위치와 시간 사이의 그래프를 그려보았는데 그 그래프에서 특정 영역의 중첩 횟수 최댓값을 구하면 된다는 것을 알게 되었다. 그래서 시간에 따른 물고기의 시작점과 끝점의 위치 식을 모두 저장해 놓고 교점을 가지고 스위핑을 하는 풀이가 가능할 것 같다는 생각이 들었다. 교점의 좌표가 분수라는 점과 $t\geq 0$인 조건 같은 교점에서 +1과 -1의 순서를 헷갈려 많은 WA를 냈다가 맞았다.