1123 : 도미노2
제한시간: 1000 ms
메모리제한: 64 MB
해결횟수: 157 회
시도횟수: 724 회
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 |
출처 : USACO 2001 Fall