[일반] 답지봤는데 어떤걸 배워가야할지모르겟음

[익명(182.231)]

골2문젠데 핵심아이디어인 트리의 지름이 되는지점

즉 그래프의 최말단 위치를 찾는 아이디어를 몰라서 답지봣는데

이 경우 이 문제에서는 뭐배워가야되는거임??

이런 아이디어는 머리좋아야떠올리는거임? 아니면 전형적으로

쓰이는 테크닉임?

[익명(211.36)]

일단 풀이가 적어도 두 개 있음. 1. dfs 2번 하기: 이거는 증명을 내 걸로 소화하면 충분함. 트리의 지름 하나가 있을 때, 아무 정점에서나 시작해서 dfs를 하고 가장 깊은 노드를 아무거나 고르면 왜 그 지름의 양 끝점이나 그것보다 더 좋거나 같은 말단점이 찾아지는지 경우를 나눠서 증명할 줄 알면 됨. 2. tree dp: 계속 나올 거임 중요함

[익명(117.111)]

ㄱㅅㄱㅅ 다른 답지보면서 2번도 공부하겟음