도미노2 > 문제은행

본문 바로가기


실전대비 Level2

1123 : 도미노2

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 145 회    시도횟수: 668 회   



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

 

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

 

e3050b66a1b29a01767400d7560a4131_1449730 

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

 

e3050b66a1b29a01767400d7560a4131_1449730
 

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

 

 


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



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


[Copy]
3
1 4
2 5
3 4
[Copy]
775





USACO 2001 Fall Cow Dominoes

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.