26126번 - 맛집 가이드 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 89 | 33 | 28 | 37.333% |
문제
윤이는 UNIST 주변의 음식점에 대한 정보를 제공하는 가이드 앱, 일명 “UNIST 가이드”를 만들기로 했다. 윤이는 근처 음식점 중에서 $N$개의 음식점을 추천하기로 정하고, 음식점에 $1$번부터 $N$번까지 번호를 붙였다.
윤이는 이 음식점들에 대한 정보를 조사하다가, 두 명의 음식 평론가 동규와 원이가 각각 $N$개의 음식점에 순위를 매긴 자료를 찾았다. 윤이는 두 순위표를 바탕으로 음식점 등급을 매기려고 한다. 음식점 등급은 어떤 양의 정수 $S$에 대해, $1$ 이상 $S$ 이하의 정수 별점으로 나타낸다. 별점이 높을수록 맛있는 음식점이라는 뜻이다.
음식점 등급은 두 평론가가 매긴 음식점 순위에 위배되지 않아야 한다. 다시 말해, 어떤 음식점 X의 등급이 음식점 Y의 등급보다 높다면, 이는 두 평론가의 순위표에서 모두 음식점 X의 순위가 음식점 Y보다 높다는 것을 의미한다. 역은 성립하지 않아도 된다.
또한, 각각의 등급에 대해서 해당 등급을 받은 음식점이 적어도 $K$개 있어야 한다.
윤이는 음식점 정보가 구체적일수록 UNIST 가이드의 신뢰도가 올라갈 것이라고 분석해서, 음식점 등급을 최대한 세분화하려고 한다. 즉, 윤이의 목표는 최고 별점 $S$가 최대한 크도록 음식점 등급을 매기는 것이다. 윤이가 조건을 만족하도록 음식점 등급을 매겼을 때 등급의 개수는 최대 얼마인가?
입력
첫 번째 줄에 음식점의 개수 $N$과 등급별 최소 음식점 개수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($1\le K\le N\le 200\ 000$)
두 번째 줄에 평론가 동규가 평가한 순위가 높은 순서대로 $N$개의 음식점 번호가 공백으로 구분되어 주어진다.
세 번째 줄에 평론가 원이가 평가한 순위가 높은 순서대로 $N$개의 음식점 번호가 공백으로 구분되어 주어진다.
주어지는 음식점 번호는 $1$ 이상 $N$ 이하의 정수이며, 각 줄 내에서 중복되지 않는다.
출력
윤이가 음식점 등급을 최대한 세분화하도록 등급을 매겼을 때, 등급의 개수를 출력한다.
예제 입력 1
8 3 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7
예제 출력 1
2
예제 입력 2
4 1 4 2 3 1 2 1 4 3
예제 출력 2
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호