14462번 - 소가 길을 건너간 이유 8 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB68537129653.237%

문제

존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.

농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.

그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.

입력

첫 줄에 N이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.

예제 입력 1 

6
1
2
3
4
5
6
6
5
4
3
2
1

예제 출력 1 

5
W3sicHJvYmxlbV9pZCI6IjE0NDYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg3NCAoXHVjNmIwXHViOWFjXHVhYzAwIFx1YzljMFx1YWUwOFx1YWU0Y1x1YzljMCBcdWIzYzRcdWM2NDAgXHVjOGZjXHVjNWM4XHViMzU4IFx1Yzg3NFx1YWNmY1x1YjI5NCBcdWIyZTRcdWI5NzggXHVjNzc4XHViYjNjXHVjNzc0XHViMmU0KVx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDBcdWIyOTQgTiBcdWM4ODVcdWI5NThcdWM3NTggXHVjMThjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxIDFcdWJjODggXHVjODg1LCAyXHViYzg4IFx1Yzg4NSwgLi4uLCBOXHViYzg4IFx1Yzg4NSAoMSAmbGU7IE4gJmxlOyAxMDAwKVx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIHxhJm1pbnVzO2J8ICZsZTsgNFx1Yjc3Y1x1YmE3NCBhXHViYzg4IFx1Yzg4NVx1YWNmYyBiXHViYzg4IFx1Yzg4NVx1Yzc1OCBcdWMxOGNcdWIyOTQgXHVjZTVjXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWIwOThcdWMwNThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjYWJkXHVjNWQwIFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1Yzc4OFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODg1XHViOTU4XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWQ1NWMgXHViYWE5XHVjZDA4XHVjOWMwXHVjNTI5IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YjNjNCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YWQ1MFx1ZDFiNVx1YzBhY1x1YWNlMFx1Yjk3YyBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Yzg3NFx1Yzc0MCBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDZhMVx1YjJlOFx1YmNmNFx1YjNjNFx1YjI5NCBcdWM2N2NcdWNhYmRcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWUzOFx1YzVkMCBcdWMyMThcdWM5YzFcdWM3N2MgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC4gXHViYjNjXHViODYwIFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWM4OGJcdWM3NDAgXHVjMThjXHViNGU0XHViMDdjXHViOWFjIFx1YzVmMFx1YWNiMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWJhYTlcdWNkMDhcdWM5YzBcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVkNmExXHViMmU4XHViY2Y0XHViM2M0XHViOWNjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWFjMDAgXHVhY2I5XHVjZTU4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM3NDQgXHViNDU4XHViN2VjXHViY2Y0XHViYTc0XHVjMTFjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1ZDZhMVx1YjJlOFx1YmNmNFx1YjNjNFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWNkMDhcdWM5YzBcdWJjYzRcdWI4NWMgXHVjMThjXHVjNzU4IFx1Yzg4NSBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Yzg4NVx1Yzc0MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDZhMVx1YjJlOFx1YmNmNFx1YjNjNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48YnI+PFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNDQ2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCBJSSAoR29sZCkiLCJkZXNjcmlwdGlvbiI6IjxwPiZuYnNwOzxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiByYWlzZXMmbmJzcDtOJm5ic3A7YnJlZWRzIG9mIGNvd3MgKDEgJmxlOyBOICZsZTsgMTAwMCksIGNvbnZlbmllbnRseSBudW1iZXJlZCZuYnNwOzEmaGVsbGlwO04uIFNvbWUgcGFpcnMgb2YgYnJlZWRzIGFyZSBmcmllbmRsaWVyIHRoYW4gb3RoZXJzLCBhIHByb3BlcnR5IHRoYXQgdHVybnMgb3V0IHRvIGJlIGVhc2lseSBjaGFyYWN0ZXJpemVkIGluIHRlcm1zIG9mIGJyZWVkIElEOiBicmVlZHMmbmJzcDthJm5ic3A7YW5kJm5ic3A7YiZuYnNwO2FyZSBmcmllbmRseSBpZiZuYnNwO3xhJm1pbnVzO2J8ICZsZTsgNCwgYW5kIHVuZnJpZW5kbHkgb3RoZXJ3aXNlLjxcL3A+XHJcblxyXG48cD5BIGxvbmcgcm9hZCBydW5zIHRocm91Z2ggRkomIzM5O3MgZmFybS4gVGhlcmUgaXMgYSBzZXF1ZW5jZSBvZiZuYnNwO04mbmJzcDtmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQgKG9uZSBkZXNpZ25hdGVkIGZvciBlYWNoIGJyZWVkKSwgYW5kIGEgc2VxdWVuY2Ugb2YmbmJzcDtOJm5ic3A7ZmllbGRzIG9uIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByb2FkIChhbHNvIG9uZSBmb3IgZWFjaCBicmVlZCkuIFRvIGhlbHAgaGlzIGNvd3MgY3Jvc3MgdGhlIHJvYWQgc2FmZWx5LCBGSiB3YW50cyB0byBkcmF3IGNyb3Nzd2Fsa3Mgb3ZlciB0aGUgcm9hZC4gRWFjaCBjcm9zc3dhbGsgc2hvdWxkIGNvbm5lY3QgYSBmaWVsZCBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZCB0byBhIGZpZWxkIG9uIHRoZSBvdGhlciBzaWRlIHdoZXJlIHRoZSB0d28gZmllbGRzIGhhdmUgZnJpZW5kbHkgYnJlZWQgSURzIChpdCBpcyBmaW5lIGZvciB0aGUgY293cyB0byB3YW5kZXIgaW50byBmaWVsZHMgZm9yIG90aGVyIGJyZWVkcywgYXMgbG9uZyBhcyB0aGV5IGFyZSBmcmllbmRseSkuIEVhY2ggZmllbGQgY2FuIGJlIGFjY2Vzc2libGUgdmlhIGF0IG1vc3Qgb25lIGNyb3Nzd2FsayAoc28gY3Jvc3N3YWxrcyBkb24mIzM5O3QgbWVldCBhdCB0aGVpciBlbmRwb2ludHMpLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgb3JkZXJpbmcgb2YmbmJzcDtOJm5ic3A7ZmllbGRzIG9uIGJvdGggc2lkZXMgb2YgdGhlIHJvYWQgdGhyb3VnaCBGSiYjMzk7cyBmYXJtLCBwbGVhc2UgaGVscCBGSiBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNyb3Nzd2Fsa3MgaGUgY2FuIGRyYXcgb3ZlciBoaXMgcm9hZCwgc3VjaCB0aGF0IG5vIHR3byBpbnRlcnNlY3QuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOLiBUaGUgbmV4dCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQ7IGVhY2ggYnJlZWQgSUQgaXMgYW4gaW50ZWdlciBpbiB0aGUgcmFuZ2UmbmJzcDsxJmhlbGxpcDtOLiBUaGUgbGFzdCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiB0aGUgZmllbGRzIG9uIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByb2FkLiBFYWNoIGJyZWVkIElEIGFwcGVhcnMgZXhhY3RseSBvbmNlIGluIGVhY2ggb3JkZXJpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGRpc2pvaW50ICZxdW90O2ZyaWVuZGx5IGNyb3Nzd2Fsa3MmcXVvdDsgRmFybWVyIEpvaG4gY2FuIGRyYXcgYWNyb3NzIHRoZSByb2FkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Gold 2번

  • 문제를 번역한 사람: jh05013

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)