USACO 2001 Fall- 도미노2 > 문제은행 : 정보올림피아드&알고리즘




1123 : 도미노2

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
161 회   
시도횟수
742 회   

문제

N(1≤N≤40)개의 도미노가 있다. 각 도미노는 직사각형으로, 위와 아래 두 부분으로 나누어져 있다. 각 부분에는 0에서 9까지 한 자리의 십진수가 적혀있다.

 

도미노를 그림으로 표현하면 아래의 그림과 같으며, 위와 아래에 적힌 숫자를 바꿀 수 있다.

 

 

도미노를 늘어놓아서 두 개의 n자리 숫자를 만든다. 예를 들어 5와 2, 3과 4, 4와 1이 적힌 도미노를 아래와 같은 식으로 늘어놓는다면, 생성 되는 수는 534와 241이다. 도미노를 늘어 놓는 순서는 아무렇게나 해도 상관 없다.

 


 

이 두 수의 합을 최대로 할 수 있는 도미노의 배치를 찾아서, 그 최대의 합을 출력하는 프로그램을 작성하라.

 

 


입력형식

첫 번째 줄에는 도미노의 개수 N(1≤N≤40)이 입력된다. 그 다음 줄부터 N+1개의 줄에는 도미노에 적힌 2개의 숫자가 입력된다. 도미노에 적힌 숫자는 0 이상 9 이하이다.


출력형식

도미노로 만들 수 있는 최대 숫자의 합을 출력한다.


입력 예

3
1 4
2 5
3 4

출력 예

775


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

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

Copyrightⓒ 2010 jungol. All right reserved.

TOP