코드
ACM 10131, Is Bigger Smarter?
ehei
2005. 12. 4. 16:14
코끼리의 체중과 아이큐를 입력받아서 체중은 증가하는 순서로, IQ는 감소하는 순서로 된 목록 중 가장 긴 것을 뽑는다.
문제: http://acm.uva.es/p/v101/10131.html
[풀이]
플로이드의 길찾기 문제로 해결할 수 있다. 다음과 같은 입력이 있다고 하자.
번호 | 체중 | IQ |
1 | 40 | 100 |
2 | 100 | 70 |
3 | 110 | 60 |
4 | 50 | 90 |
아래 그림은 각 번호가 연결될 수 있는 지점을 나타낸 것이다. 즉, 1번 뒤에는 모든 코끼리가 위치할 수 있고 3번 뒤에는 어떤 코끼리도 올 수 없다.
결국 이것은 플로이드의 최단 경로를 반대로 해석하여 해결 할 수 있다. 최장 경로를 찾으면 되는 것이다.
1133680508_Is Bigger Smart.cpp