악수 > 문제은행

본문 바로가기


알고리즘 다이나믹1

1235 : 악수

제한시간: 2000 ms    메모리제한: 64 MB
해결횟수: 702 회    시도횟수: 1668 회   



마을의 연중 행사가 열렸다. 마을 사람들은 둥근 테이블에 둘러 앉아 있다. 전통적으로 이 행사에서는 테이블에 둘러 앉아서 악수를 한다. 한 사람은 다른 한 사람과 악수를 꼭 해야 한다. 이렇게 모든 사람이 동시에 악수를 하는데, 단, 악수하는 팔이 서로 교차해서는 안 된다. 그림은 팔이 교차하지 않는 경우와 교차하는 경우를 보여주고 있다.


7ce7f2eba5731c8babe39036322897a0_1449819

 


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


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



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


[Copy]
6 
1 2 2 1 3 3
[Copy]
3


[Copy]
22 
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9
[Copy]
6




The 2006 Benelux Algorithm Programming Contest The Bavarian Beer Party, poj 3056

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.