선긋기
-
[백준 BOJ/C++] 2170 선긋기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 6. 00:46
2170번: 선긋기 문제도 상당히 단순하고 쉬워보이지만 의외로 골드등급의 문제고 정답비율도 30% 대로 높지 않은편이다. 구현양도 얼마 안되지만 이러한 스타일의 문제를 많이 접해보지 않았다면 아이디어를 찾는데 어려움을 겪을 수도 있는 문제다. 문제는 정말 심플하다. 여러 선의 시작점과 끝점을 받아서 선들의 전체 길이를 구하면 된다. 하지만 이 선들은 일직선 상에 겹칠 수 있게 그려지며 따라서 겹쳐진 구간과 선이 그어지지 않은 구간을 제외한 실제전체 길이를 구해야 한다. 주어지는 값들의 범위도 꽤 크다. 점의 위치는 -1,000,000,000 ~ 1,000,000,000 사이이며 선의 수는 최대 1,000,000 으로 효율적으로 해결할 방법을 찾아야 한다. 문제의 포인트 아이디어 찾기 문제가 단순한 만큼 ..