http://acm.uva.es/p/v1/103.html
긴 육각 입체가 있다고 생각해보자. 또 다른 긴 육각 입체가 있으나 앞의 것보다는 작다. 전자에 후자를 넣으려면 어떻게 해야할까? 가능한 모양을 비슷하게, 즉 둘다 길게 넣는 편이 더 잘 들어갈 것이다. 이것은 모든 n 차원에 동일하게 적용된다.
따라서 입력된 n 차원의 값을 정렬하면 - 형태를 비슷하게 만들면 - 최장거리 구하기가 된다. 이제는 플로이드 알고리즘을 적용하기만 하면 된다.
'코드' 카테고리의 다른 글
ACM 101, The Blocks Problem (0) | 2005.12.22 |
---|---|
ACM 100, 3n + 1 (0) | 2005.12.22 |
ACM 10069, Distinct Subsequences (0) | 2005.12.17 |
ACM 10131, Is Bigger Smarter? (0) | 2005.12.04 |
Floyd의 최단 경로 구하기 (0) | 2005.11.27 |