최고 속력 600 km/h로 운행하는 것을 목표로 하는 ‘한국형 초고속철도 사업’이 순조롭게 진행되고 있다.

이미 초고속철도의 시험선로를 구축하였고 열차를 시험운행하고 있다.

그리고 선로의 상태를 검사하기 위하여, 선로의 지정된 검사구간을 담당하는 로봇을 설치하였다.

그런데 검사구간이 서로 겹치는 로봇 사이에는 빈번한 데이터 교환이 필요하다.

따라서 이를 지원할 데이터 송수신 장치를 모든 로봇에 설치할 뿐만 아니라, 특별한 데이터 처리장치를 로봇에 부착하기로 하였다.

그러나 이 처리장치는 모든 로봇에 부착하지 않아도 되지만,

두 로봇이 담당하고 있는 검사구간이 서로 겹치면 이 두 로봇 중에서 적어도 하나에는 반드시 부착되어야 한다.

아래 그림과 같은 시험선로에서 네 개의 로봇 a, b, c, d가 있고, 각 로봇의 검사구간은 아래와 같다고 하자.

로봇 a와 b는 담당하는 선로의 검사구간이 겹치므로 둘 중 최소한 하나에 처리장치가 부착되어야 한다.

로봇 b와 c, b와 d, 그리고 c와 d의 경우도 마찬가지이다.

위의 조건을 만족하면서 처리장치를 부착하는 것은 여러 가지 경우가 있을 수 있다.

위 그림의 예에서 {a, b, c, d} 모두에 부착할 수도 있고, {b, c}에 부착할 수도 있다.

우리 팀에서는 어떤 로봇에 처리장치를 부착하는 것이 좋은 지를 연구하고 있는데,

우선 위 조건을 만족하면서 처리장치를 부착할 수 있는 모든 경우의 수를 구하여 보기로 하였다.

위의 예에서 가능한 경우를 모두 나열해보면 {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {b, d}, {b, c}, 총 일곱 가지 경우가 있다.

시험선로를 눈금이 매겨진 직선으로 나타내며, 로봇의 검사구간은 이 직선 위에 있다고 할 때,

로봇들이 담당하는 선로의 검사구간을 입력 받아 로봇에 처리장치를 부착할 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하시오.

초고속철도 timer 1초 memory 64MB

초고속철도 1초 64MB