선분 그리기 > 문제은행



문제은행

1251 : 선분 그리기

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 2 회    시도횟수: 3 회   



오늘도 열심히 공부하던 진돌이는 좌표평면에 수많은 수직/수평 선분들을 그리느라 지쳐버렸다. 특히 펜을 들었다 뗐다 하는 일이 너무나 귀찮았던 진돌이는 될 수 있으면 펜을 조금 들었다 놓으면서 모든 선분들을 그리고 싶었다.

예를 들어, 5개의 선분으로 구성된 아래 그림을 보면

 

e3050b66a1b29a01767400d7560a4131_1449742
 

 

펜을 한 번도 떼지 않고 똑같이 그릴 수 있다. 따라서 펜을 뗀 횟수는 0회이다. 그런데 문제는 진돌이가 가진 펜의 두께가 너무 얇아서 같은 선분을 여러 번 색칠해야 할 것 같다. 반복해서 색칠할 횟수와 선분들이 주어질 때 펜을 최소한 몇 번 들었다 놓아야 하는가?

단, 선분들이 겹쳐도 알아내고자 하는 건 선분들이 이루는 모양이기 때문에 여러 번 덧칠할 필요는 없다.




첫 행에는 두 자연수 선분의 수 N과 반복할 횟수 M이 주어진다. 선분의 수는 50개 이하이며, 반복할 횟수는 1,000,000번 이하이다.

다음 N 개의 행에 걸쳐 각 선분의 양 끝 점의 좌표가 주어진다. 좌표는 -1,000,000 이상 1,000,000 이하의 값이다. 모든 선분은 축에 대해 수직 또는 수평하다.




최소 펜을 드는 횟수를 출력한다.



2 1 
-10 0 10 0 
0 -10 0 10
1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.