엘리베이터 > 문제은행

본문 바로가기


실전대비 Level5

1425 : 엘리베이터

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 94 회    시도횟수: 406 회   



N층으로 이뤄진 고층 아파트에 M대의 엘리베이터가 있다. 각 엘리베이터에는 1부터 M까지 번호가 매겨져있다.

 

아파트 관리인은 유지비를 줄이기 위하여 각 엘리베이터가 특정한 층에서만 서도록 하였다. 그 결과 i번 엘리베이터는 Xi번째 층에서부터 시작하여 매 Yi번째 층에서만 선다. 예를 들어 Xi = 4, Yi = 3이라면 i번 엘리베이터는 4층, 7층, 10층, …에서만 서게 된다.

 

이 아파트 A층에서 사는 철수는 B층에 있는 친구 집에 놀러 가려고 한다. 그런데 가능하면 엘리베이터를 타는 횟수를 줄이고 싶어 한다.

 

예를 들어 아파트가 총 12층이고, 엘리베이터가 3대 있으며, 각 엘리베이터가 다음과 같이 운행한다고 하자.

 

 

e3050b66a1b29a01767400d7560a4131_1449744
 

 

10층에서 8층으로 가기 위해서는 1번 - 2번 - 3번 엘리베이터를 차례로 탈수도 있고, 1번 - 3번 엘리베이터를 탈수도 있다. 어떤 방법이든 최소 두 번 엘리베이터를 타야한다.

 

N과 M 그리고 엘리베이터 운행 정보가 주어질 때 철수가 최소 몇 번 엘리베이터를 타야하는지와 타야할 엘리베이터의 순서를 구하는 프로그램을 작성하시오.


>입력 파일의 첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다.
둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. 
N은 100,000이하, M은 100이하의 자연수이며, Xi, Yi, A, B는 모두 N이하의 자연수이다.


첫째 줄에는 A층에서 B층으로 가기 위해 최소 몇 번 엘리베이터를 타야하는지를 출력한다. 
다음 줄부터 타야하는 엘리베이터의 번호를 한 줄에 하나씩 타는 순서대로 출력한다. 
또한 엘리베이터를 타는 방법이 여러 가지인 경우에는 그 중의 한 방법만을 출력한다. 
만약 A층에서 B층으로 갈 수 없다면 첫째 줄에 -1을 출력한다.

[Copy]
12 3
4 3
7 5
4 4
10 8
[Copy]
2
1
3






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.