문제
롤은 이제 재미 없어졌고 오버워치는 나이 제한에 걸려 게임을 못하게 된 정현C는 보드게임에 눈을 돌렸다.
요즘 관심있는 보드게임은 블록 쌓기이다. 게임의 룰은 간단한데 참가자 모두에게 같은 구성 같은 개수의 직육면체 블록이 N개씩 주어진다.
참가자는 자신이 받은 N개의 블록들 중 일부 또는 전부를 임의로 선택하여 면들이 닿게 일렬로 쌓는 것이다.
블록은 마음대로 회전시켜 쌓을 수 있지만, 마치 하노이 탑 쌓기와 유사하게 아래쪽 블록은 위쪽 블록보다 가로, 세로 길이가 모두 크거나 같아야 한다.
높게 쌓을 수록 점수가 높다고 한다.
어떻게 하면 정현이가 우승할 수 있을까?
정현C가 받은 블록 정보를 이용하여 가장 높이 쌓을때 높이를 구해보자.
입력
첫 행에 테스트 케이스의 수 TC ( 1 <= TC <= 50)가 입력된다.
다음 행 부터 각 테스트 케이스에 대한 데이터가 입력되는데 각 테스트 케이스의 첫 행에는 상자의 개수 N( 3 <= N <= 20)이 주어진다.
다음 N개 행에 N개의 블록 정보가 주어지는데 하나의 행에는 각 블록의 가로, 세로, 높이를 나타내는 wi, hi, di( 1 <= wi, hi, di <= 100)가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대하여 행으로 구분하여 N개의 블록들 중 일부 또는 전부를 사용하여 가장 높게 쌓을 때 높이를 출력한다.
예제
2
4
2 6 4
2 4 3
5 4 3
1 4 4
5
1 5 6
2 6 10
1 7 9
2 6 10
5 5 5
18
27
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.