전 당연하게 path cover로 풀어야겠구나 해서 path cover로 풀었는데(문제 특성상 O(n)에 최대 매칭을 찾을 수 있으므로)
설명이나 소스 코드를 보니깐 다른분들은 더 쉽게 접근하신 것 같네요.
아무리 봐도 잘 이해가 가질 않아서 그러는데 약간 설명좀 부탁드립니다. ㅠ
죄송합니다 ㅠㅠ
저 너무 설명을 못하는거 같아요.
음 저도 path cover를 이용하기 했는데, 다만 인터벌들이 있기 때문에 걍 정렬해놓고 되는대로 붙여나가면 된다고 봐서 그렇게 풀었는데요,,
"문제 특성상 O(n)..." 이 말씀대로 전 풀었는데(에디토리얼에 있는거가..) 결국 같은 방법으로 한거 같습니다.
저는 이렇게 풀었습니다.
인터벌들을 그래프로 나타내고 겹치는 걸 엣지를 그으면 결국 거기서 최소 컬러링을 찾는 문제랑 같아지는데요,
인터벌 그래프에서 최소 컬러링은 그냥 가장 구간이 많이 겹치는 곳이므로
주어진 구간들 중에 가장 많은 구간이 겹치는 곳을 찾으면 끝입니다.
그건 뭐 .. 그냐
ibroker
전 당연하게 path cover로 풀어야겠구나 해서 path cover로 풀었는데(문제 특성상 O(n)에 최대 매칭을 찾을 수 있으므로)
설명이나 소스 코드를 보니깐 다른분들은 더 쉽게 접근하신 것 같네요.
아무리 봐도 잘 이해가 가질 않아서 그러는데 약간 설명좀 부탁드립니다. ㅠ
17년 전