-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...