17280번 - 카풀 매칭 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 417 | 92 | 70 | 29.289% |
문제
당신은 친구를 도와 새로운 카풀 앱을 개발해야 한다. 그 중 운전자와 승객을 매칭 시켜주는 알고리즘을 당신이 개발해야 한다. 현재 이 앱은 베타 버전이기 때문에 동-서로 길게 늘어진 고속도로 위에 위치한 지역에서만 서비스를 하고 있으며 아래와 같은 제한이 있다.
- 모든 운전자와 승객은 가장 동쪽에 위치한 “출발지" 도시에서 출발한다.
- 총 N명의 승객이 있으며, i번째 승객은 출발지에서 서쪽으로 xi 미터 떨어진 곳에 위치한 목적지에 가고 싶어한다 (0 < xi).
- 총 M명의 운전자가 있으며, j번째 운전자는 출발지에서 서쪽으로 yj 미터 이상 zj 미터 이하 떨어진 곳 사이에 가고 싶어하는 승객을 최대 한 명 태워줄 의향이 있다 (0 < yj ≤ zj).
당신은 이 조건들을 만족하면서 최대한 많은 승객-운전자를 매칭시키는 알고리즘을 작성해야 한다.
예를 들어, 3명의 승객과 3명의 운전자가 있을 때, x, y, z 값이 아래와 같다고 하자.
- x = [10, 20, 30]
- y = [8, 2, 25]
- z = [8, 18, 35]
이 경우 승객 1, 2, 3은 각각 정확 10미터, 20미터, 30미터 떨어진 곳으로 가고 싶어하며, 운전자 1은 정확히 8미터 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 2는 2미터 이상 18미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 3은 25미터 이상 35미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있다.
이 경우, 승객1-운전자2, 승객3-운전자3을 매칭시켜주면 총 두 쌍을 매칭시킬 수 있고 이보다 많은 수의 승객-운전자를 매칭 시킬 수 있는 방법은 없다.
입력으로 N, M, 그리고 x, y, z 값들을 입력 받아 최대한 많은 승객-운전자 쌍을 매칭시키면 몇 쌍을 매칭 시킬 수 있는지 계산하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스의 첫 줄에는 N, M 이 주어진다.
그 다음 줄에 xi 가 공백으로 구분되어 주어진다 (1 ≤ xi ≤ 1,000,000,000).
다음 M줄에 걸쳐 각 줄에 yj 와 zj 가 공백으로 구분되어 주어진다 (1 ≤ yj ≤ zj ≤ 1,000,000,000).
출력
각 테스트 케이스에 대해, 최대한 많은 승객-운전자를 매칭 시켰을 때 몇 쌍을 매칭시킬 수 있는지 출력한다.
서브태스크 1 (7점)
- 1 ≤ N, M ≤ 100
서브태스크 2 (13점)
- 1 ≤ N, M ≤ 100,000
예제 입력 1
3 3 3 10 20 30 8 8 2 18 25 35 4 4 2 3 4 5 1 4 2 4 3 5 3 4 3 3 1 2 3 10 20 30 40 50 60
예제 출력 1
2 4 0
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호