1839번 - 트리 모델 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 144 | 54 | 39 | 33.051% |
문제
월드 장난감 회사는 노끈들을 이용해서 트리의 모형을 만들고자 한다. 이를 돕기 위한 프로그램을 작성하라.
트리 (tree)는 그래프 (graph)의 일종으로, 연결되어 있으며, 내부에 싸이클이 존재하지 않는 그래프이다. 그래프에서 버텍스 (vertex), 에지 (edge)라고 부르는 것을, 트리에 한해서는 각각 노드 (node)와 링크 (link)라고 부른다.
트리의 노드들은 노끈 위에 매인 매듭으로 표현되고, 각 매듭 사이를 연결하는 노끈이 트리의 링크들을 표현한다. 노드를 표현하는 매듭들은 그냥 한 개의 노끈 중간이나 끝부분을 묶은 것일 수도 있고, 여러 개의 노끈들이 한 점에서 뭉쳐 묶여 있는 부분일 수도 있다.
기술적인 문제 때문에, 생산 단가는 모델을 만드는 데 사용되는 노끈의 개수와, 사용된 노끈들 중 가장 긴 노끈의 길이에 의존한다. (각각의 링크들은 길이가 모두 1이다. 매듭을 만드는 데 소요되는 노끈의 길이는 무시한다.)
여러분이 할 일은 첫째, 트리의 구조가 주어지면 이를 만들기 위한 최소의 노끈 개수를 구하는 것이다. 둘째로는, 이와 같이 최소 개수의 노끈들을 이용하여 트리를 만들 때 사용되는 가장 긴 노끈 길이의 최솟값을 구하는 것이다.
입력
첫째 줄에 노드의 개수를 나타내는 양의 정수 n이 주어진다. (2≤n≤10,000) 둘째 줄부터는 n-1개의 링크를 나타내는 두 개씩의 양의 정수가 주어진다. 각각은 링크가 연결 짓는 두 노드의 번호를 나타낸다. 노드의 번호는 1번부터 n번까지 빠짐없이 연속하여 붙어 있다.
출력
첫 줄에 필요한 최소한의 노끈 개수와, 가장 긴 노끈 길이의 최솟값을 출력한다.
예제 입력 1
9 7 8 4 5 5 6 1 2 3 2 9 8 2 5 5 8
예제 출력 1
4 2
힌트
출처
Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 1 2번
- 문제를 번역한 사람: author10
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호