14459번 - 소가 길을 건너간 이유 11 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 282 | 169 | 142 | 63.111% |
문제
우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의 농장을 방문한 것이었다. 그 사이에 우리가 도와주려고 했던 존은 자신의 코드를 아무리 디버깅을 해 봐도 틀렸습니다나 런타임 에러가 나서 포기하고 제2안을 시도하고 있다.
존은 최근에 일부 종은 친하다는 것을 알게 되었다. 존의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.
존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명할 것이다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.
그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.
입력
첫 줄에 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.
출력
조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.
예제 입력 1
6 1 2 3 4 5 6 6 5 4 3 2 1
예제 출력 1
5
출처
Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Platinum 2번
- 문제를 번역한 사람: jh05013
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호