ACM 103, Stacking Problem

http://acm.uva.es/p/v1/103.html

 

긴 육각 입체가 있다고 생각해보자. 또 다른 긴 육각 입체가 있으나 앞의 것보다는 작다. 전자에 후자를 넣으려면 어떻게 해야할까? 가능한 모양을 비슷하게, 즉 둘다 길게 넣는 편이 더 잘 들어갈 것이다. 이것은 모든 n 차원에 동일하게 적용된다.

 

따라서 입력된 n 차원의 값을 정렬하면 - 형태를 비슷하게 만들면 -  최장거리 구하기가 된다. 이제는 플로이드 알고리즘을 적용하기만 하면 된다.

1134899019_input.txt

1134899019_Stacking Boxes.cpp