[BOJ] 3116번: MIKRO

https://www.acmicpc.net/problem/3116

 

일단 모든 박테리아 쌍에 대해 충돌 시간을 계산해두고 (충돌 시간, 박테리아 번호1, 박테리아 번호2) 이 tuple을 충돌 시간 순으로 정렬합니다.

 

이후 충돌 시간이 동일한 충돌 쌍들을 보며 rank를 계산할 수 있습니다. rank를 계산하는 방법은 아래와 같습니다.

 

예를 들어 3초에 (1, 2), (1, 4), (2, 4), (6, 7)이 충돌했다고 합시다. 그러면 우선 해당 pair에서 등장한 수들의 목록을 따로 저장합니다.(1, 2, 4, 6, 7)

 

그 후 (1, 2)를 보며 cnt[1], cnt[2]를 1 증가해주고, (1, 4)를 보며 cnt[1], cnt[4]를 증가해주고.. 이렇게 cnt를 다 증가시킵니다.

 

마지막으로 (1, 2, 4, 6, 7)에 대해 cnt[i]+1이 rank이고 이를 계산한 후 cnt[i]를 0으로 초기화시킵니다.

 

https://github.com/blisstoner/BOJ/blob/master/3116.cpp