어려웠다1 [KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회) 이 풀이는 homebody님의 풀이를 보고 이해하며 작성한 것입니다. 처음에는 줄세우기 문제와 비슷하다고 생각했는데, 누가 더 잘 하고, 못하고에 맞춰서 정렬하는 건 쉽지만 그 범위를 알아내는 건 어려웠다. 그래서 반대로 root 노드로부터 떨어진 거리를 각각 기록하고, 각 정점의 자식 수를 기록해서 같은 거리에 있는 그래프들의 순위 변화에 따라서 어떻게 등수가 바뀌는지 계산하려고 했지만 구현이 까다로울 뿐더러 연결 그래프가 2개 이상인 경우에는 답도 구할 수 없어서 결국 풀이를 봤다. 아이디어는 간단한데, 그래프를 두 개로 분리해서 "나보다 등수가 높은 그래프"와 "나보다 등수가 낮은 그래프"로 관리하는 것이다. (이걸 어떻게 생각했을까...) 예를 들어서 경민이가 형곤이보다 등수가 높다고 해보자. 그.. 2019. 12. 28. 이전 1 다음
