2617번: 구슬 찾기 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 N개의 구슬들의 무게를 비교한 정보가 M개 있을 때, 이를 가지고 무게가 중간일 수 없는 구슬의 수를 구하는 문제다. 기본적인 개념은 i번 구슬보다 무거운 구슬의 수나 가벼운 구슬의 수가 N/2보다 크면 그 구슬은 중간일 수 없다. 따라서 각 구슬 간의 무게를 모두 비교하기 위해 플로이드-워셜 알고리즘을 사용했다. 무게 관계 a, b는 a가 b보..