바빌론

공중 정원을 별개로 하더라도, 고대 바빌로니아인들은(B.C. 3000-539년경) 바빌론 탑을 쌓았다. 탑은 하늘까지 도달할 작정이었으나, 그 프로젝트는 언어의 혼란으로 인하여 실패하였다. 2638주년을 기념하여 탑의 모델이 재건될 예정으로 있다. n 개의 서로 다른 종류의 (직육면체 모양의) 블록을 이용할 수 있다. 각각은 당신이 원하는 만큼 복제하여 사용할 수 있다. 각 블록은 가로가 x, 세로가 y, 그리고 높이가 z이다. 한 블록위에 블록을 하나씩 쌓아서 최종적으로 만들어진 탑의 높이를 최대로 하려고 한다. 물론 블록을 회전하여 쌓을 수 있다. 그렇지만 블록의 밑면을 이루는 두 변은 x,y-축에 평해하여야 하며, 안정성 때문에 아래쪽 블록의 두변 모두가 각각 위쪽 블록의 해당 변의 길이보다 더 작을 때에만 블록을 쌓을 수 있다.

블록의 가짓수와 각 블록의 세 변의 길이가 입력으로 주어질 때, 주어진 제약 조건을 만족하면서 가장 높이 쌓을 수 있는 탑의 높이를 구하는 프로그램을 작성하시오.

프로그램 이름은 babylon.cpp, 실행 파일의 이름은 babylon.exe, 프로그램 설명 파일 이름은 babylon.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 블록의 종류 n을 나타내는 정수가 주어진다. 뒤이은 n개의 줄에는 각 블록의 가로 길이 xi, 세로 길이 yi, 그리고 높이 zi를 나타내는 정수들이 빈칸을 사이에 두고 순서대로 주어진다. 블록의 종류는 30개를 넘지 않는다.

2004 가을학기 문제해결기법	문제 #4

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 가장 높이 쌓을 수 있는 탑의 높이를 한 줄에 출력한다.

입력과 출력의 예

입력(input.txt)

5

31 41 59

26 53 58

97 93 23

84 62 64

33 83 27

출력(output.txt)

342