기로에 서다

문제 https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 1. 0번부터 n - 1번까지 중앙 정점을 옮겨가며 매번 거리를 계산하는게 아니라 0번 정점과 그 외 정점사이의 거리를 구한 후, 중앙 정점을 옮길 때마다 추가/감소되는 비용만 구하면 최소거리인 중앙정점을 구할 수 있습니다. 2. 정점을 옮길 때마다 추가/감소되는 비용은 정점과 연결된 간선들의 개수와 관련이 있고, 이는 dfs를 돌려 연결된 간선개수를 찾을 수 있습..

문제 programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 1. +, -하는 가중치가 같기에 모든 가중치의 합이 0이여야 결국 0으로 만들 수 있습니다. 따라서 0이 아니면 -1을 반환합니다. 2. 조금만 생각해본다면 연결된 두 점에 대해서 연산할 때, 리프부터 처리해서 루트로 올라와야 빠짐없이 0으로 만들 수 있습니다. 3. 트리임이 보장되었기에 0번노드를 루트로 잡고 dfs를 돌리는데 리프노드에선 연산..

문제 www.acmicpc.net/problem/7045 7045번: Tree Cutting After Farmer John realized that Bessie had installed a "tree-shaped" network among his N (1