악수 > 문제은행



1235 : 악수

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
761 회   
시도횟수
1817 회   

문제

마을의 연중 행사가 열렸다. 마을 사람들은 둥근 테이블에 둘러 앉아 있다. 

전통적으로 이 행사에서는 테이블에 둘러 앉아서 악수를 한다. 한 사람은 다른 한 사람과 악수를 꼭 해야 한다. 

이렇게 모든 사람이 동시에 악수를 하는데, 단, 악수하는 팔이 서로 교차해서는 안 된다. 

그림은 팔이 교차하지 않는 경우와 교차하는 경우를 보여주고 있다.


7ce7f2eba5731c8babe39036322897a0_1449819

 


각 사람은 자기가 좋아하는 맥주 브랜드를 가지고 있다. 같은 브랜드를 좋아하는 사람끼리 악수하는 편이 좋다. 

팔이 교차하지 않게 모두가 악수하는 방법 중에 같은 브랜드를 좋아하는 사람 끼리 악수하는 수가 제일 많은 방법을 찾아라.


입력형식

입력은 짝수 p로 시작한다. 2≤p≤1,000: 참가자의 수. 다음 줄에는 각 사람이 좋아하는 맥주의 브랜드 번호가 시계방향으로 주어진다. 브랜드 번호는 1부터 100까지의 정수이다.


출력형식

규칙을 만족하는 악수 방법 중에 같은 브랜드를 좋아하는 사람끼리 악수한 수의 최대값을 출력한다.


입력 예

6 
1 2 2 1 3 3

출력 예

3

입력 예

22 
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9

출력 예

6


다이나믹

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP