ACM 10131, Is Bigger Smarter?

코끼리의 체중과 아이큐를 입력받아서 체중은 증가하는 순서로, 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