[JAVA] 3의 배수2 (난이도:고급)

DESCRIPTION

주어진 숫자들을 조합하여 가장 크게 만들어 낼 수 있는 3의 배수를 출력하시오. (모든 숫자를 사용하지 않아도 됨)

 

INPUT

* Line 1 : 테스트케이스 T (1~1,000)

* Line 2 ~ T+1 : 문자열 (공백으로 구분된 숫자; 숫자의 개수는 100개를 넘지 않음)

OUTPUT

* Line 1 ~ T : 3의 배수

 - 3의 배수가 없을 경우 0을 출력

SAMPLE INPUT

1
0 1 6 7 8

SAMPLE OUTPUT

8760

comment

이전 문제와 다른 점은 모든 숫자를 사용하지 않는다는 점입니다.

원래 모든 자릿수를 더한 값이 3의 배수이면 그 숫자도 3의 배수임이 증명되어 있는데요, 

이번에는 3의 배수가 되면서 가장 큰 수를 찾아야 하는 반면, 저번엔 3의 배수인 것은 이미 확정이고 가장 큰 수를 만들기만 하면 되는 간단한 문제였습니다.

생각하느라 시간이 오래 걸렸던 문제입니다.