[BOJ 1671]

문제 바로가기 : https://www.acmicpc.net/problem/1671
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

이 문제도 BOJ 1017: 소수 쌍처럼 대상이 주어지지 않아서 조건에 맞춰 설정해야 한다.
하지만 상어를 먹을 수 있는 조건에만 맞춰 대상을 추가한다면 문제를 푸는데 굉장히 어려워질 수 있다.
알고리즘을 수정해보면서 답을 찾아보려고 하다가 굉장히 삽질했었는데 왜 어려워지는지 정리를 해봤다.

1. 이 문제의 경우 당연히 본인을 선택할 수는 없다. 또, A가 B를 선택했다면 B는 A를 선택할 수 없다.
   
2. 살아남는 상어의 수가 최소가 되도록 구해야 한다. 이분 매칭 알고리즘은 최대한 쌍을 지을 수 있도록 해주는 성능을 보인다.
   (알고리즘의 특성과 문제 방향과 일치한다)
   
3. A, B, C, D 순으로 있고 A -> B, C, D / B -> A, C, D 가 가능하다고 하자.
   그럼 처음에는 A는 B, C를 선택하게 된다. 그 다음 B로 넘어갔을 때 A를 먼저 선택한다. 여기서 문제가 발생한다.
   A가 B, C를 선택했으므로 from[B]=A, from[C]=A 이다. 근데 B가 A를 선택하면 from[A]=B가 된다. ???
   상어는 서로를 먹을 수 없다. 그렇다고 이분 탐색 함수 내에서 from[]값을 추가로 조작하면 재귀 호출때문에 순서가 망가진다.
   
   
   그래서 이렇게 저렇게 시도도 해보고 많은 고민을 해봤다. 이분 탐색말고 다른걸로 풀기엔 이분 탐색 성능이 너무 최적이다.
   최종적인 결론은 대상을 많이 갖는 녀석이 가장 위로 오도록 정렬하고, 대상은 본인 다음 순번부터 담도록 해야한다.
   대상을 가장 많이 가지려면 성능이 가장 좋으면 된다. 때문에 정렬 기준을 다음과 같이 해준다.
   

   struct shark {
    int a, b, c;
   
    bool operator<(const shark& s) const {
        if (a == s.a && b == s.b) return c > s.c;
        if (a == s.a) return b > s.b;
        else return a > s.a;
    }
   };
   

   input을 모두 받은 후 정렬해주고, 이분 탐색을 2번 해주면 된다.