문제해결: 1시간
저번에 푼 회의실배정? 문제와 비슷하다고 생각헀다. 문제가 기억이 안날거같으니 미리 써놔야지
매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.
이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.
입력
첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
라고한다 일단 범위부터 보자 1000000이다 무언가 NlogN을 원한다는거겠다라고 생각하며 x,y범위를생각하니까 int로 될거같지않다. long을 생각했다.
문제풀이
선을 그을때 한점에서 다른 한점까지 긋게 된다고 한다. 하지만 겹쳐서 그릴수도있는데 여러번 그은곳과 한번 그읏곳의 차이를 구별할수없다고한다. 중복되는 경계선이 없다는 가정하에 겹친다면 한줄로 생각해도된다라는거같다. 그랬을때 그려진 선들의 총 길이를 구하라고 하였다.
그리고 입력
5
1 3
2 4
이런식으로 주어지는거같다. 내가 먼저 접근했던 방식은 아마 어떻게하면 총 길이를 구할수 있을까부터 생각하였고 그 다음엔 어떻게하면 겹쳐지는걸 한줄로 의식할수있을까였다. 시작되는점과 끝나는점 그 사이에 무수한 줄이 있어도 끝나는점 기준이 엄청 길다면 똑같은 한줄이다. 그렇게된다면 아마 시작되는 점, 끝나는 점을 모두 고려하였을때 다른 시작점이 해당하는 시작되는점, 끝나는점 사이에 있으며 다른 끝나는점이 해당 끝나는점보다 길다면 그건 총길이가 늘어나는거라고 생각한다.그니까 내가 하고싶은말은
1------5
3-------7
이러면 해당 1,5면 3은 그사이에있으니 상관없지만 끝나는점이 7이라는점이보면 어쩄든 중복된다고 생각한다. 그러면 쉽게 끝나는점만 바꾸면된다. 마치 1-----7인것처럼 말이다. 오 나는 이걸 어떻게 생각했을까란 생각이 드니 내가 지금 현재 선택한 선이 끝나는점이 제일 긴가? 를 생각하면될일같다. 즉, 니가 고른 현재의 끝나는점이 다른점시작점안에 해당되어있으면 끝나는점이 큰가? 이다. 오오 그러면 문제가 풀릴거같다. 그러면 니가 고른 현재의 끝나는점이 제일긴가?의 예외도 고려한다면 니가 고른 현재의 끝나는점보다 다른 점의 시작점이 더 길다면? 새로운 줄이라는거다. 이렇게됐을땐 선을 바꿔야되지않을까? 왜냐면 다음 시작점은 현재 끝나는점보다 무조건 크다는의미라는거다. 여기서 의문이든다. 왜 무조건 크냐? 라고 물어볼수있는데 두점을 입력받았을떄 나는 시작점과 끝나는점을 무조건 정렬 시킬거다. 그런이유로 이런문제의 템플릿을 따지자면 어떻게 설명해야할까?
제한된 크기안에서 겹쳐진 모든 선들의 길이를 알고싶을땐 현재 내가 갖고있는 선의끝나는점이 다른 끝나는점보다 크냐? 크지않냐? 라고 생각하면 풀수있지않을까란 생각이든다.
