2898번 - 고대 자물쇠 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 213 | 46 | 41 | 23.164% |
문제
한중혁은 자신의 몬스터 트럭으로 도시의 절반을 날려버린 대가로 유명한 고고학자의 조수로 일하게 되었다. 그의 임무 중 하나는 고대 문서 상자의 열쇠를 만드는 일이다.
고대 문서 상자는 흥미로운 자물쇠가 달린 정교한 매커니즘으로 구성되어있다. 각각의 자물쇠는 너비 W cm, 높이 L cm 이며 상단부, 하단부, 그리고 이 둘 사이의 빈 공간으로 구성되어있다. 상단부와 하단부는 음이아닌 정수의 수열 r1, r2, r3, ..., rL로 나타내진다.
각 자물쇠에 맞는 열쇠는 가장자리 사이의 공간에 완벽하게 맞는 작은 점토 탭으로 되어있다. 아래 그림은 7cm X 8cm 형태의 자물쇠와 이에 맞는 열쇠를 나타낸다. 상단부를 나타내는 수열은 {2, 1, 3, 2, 3, 2, 3}이며 하단부를 나타내는 수열은 {3, 4, 2, 3, 2, 3, 4}이다.
한중혁은 하나의 열쇠가 두 개 이상의 자물쇠를 열 수도 있다는 것을 발견했다. 열쇠를 만드는 작업은 매우 힘들기 때문에 최소한의 열쇠로 모든 자물쇠를 열고자 한다. 한중혁의 작업을 덜어주기 위해, 최소 몇 개의 열쇠를 만들어야 하는지 알려주자.
입력
입력의 첫 번째 줄에는 자물쇠의 너비 W (1 ≤ W ≤ 108), 자물쇠의 길이 L (1 ≤ L ≤ 1000), 그리고 자물쇠의 개수 N (1 ≤ N ≤ 100)이 주어진다.
다음 2N개의 줄은 자물쇠의 정보를 나타낸다. 각 줄은 W보다 작은 L개의 수로 구성되어 있으며 상단부를 나타내는 수열과 하단부를 나타내는 수열이 주어진다. 모든 자물쇠는 상단부와 하단부 사이에 적어도 1cm의 빈 공간이 존재한다.
출력
한중혁이 만들어야 할 열쇠의 최소 개수를 출력한다.
예제 입력 1
8 7 2 2 1 3 2 3 2 3 3 4 2 3 2 3 4 3 2 4 3 4 3 4 2 3 1 2 1 2 3
예제 출력 1
1
예제 입력 2
8 4 4 3 3 3 3 3 3 3 3 2 2 2 2 4 4 4 4 1 2 3 4 4 3 2 1 1 1 1 1 5 5 5 5
예제 출력 2
2
예제 입력 3
100000000 2 2 88888888 88888888 4 4 4 4 88888888 88888888
예제 출력 3
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호