8169번 - 소화기 설치 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 310 | 53 | 29 | 14.216% |
문제
Byteasar는 새로운 궁전을 지었다. 그 궁전은 N개의 방과 N-1개의 통로가 방을 잇고 있다. 각각의 통로는 정확히 두 개의 방을 연결한다. 방은 1부터 N까지 번호를 가지며, 궁전으로 가는 유일한 입구는 1번 방이다. 모든 방은 입구에서부터의 경로가 유일하다. 즉, 방들은 트리 구조를 이루고 있다.
이 궁전의 소방국장은 건물 내부에 소화기를 배치하려 한다. 그는 다음의 규칙대로 소화기를 배치할 것이다.
- 소화기는 방 안에 배치되어야 하며, 하나의 방은 소화기를 몇 개라도 가질 수 있다.
- 하나의 소화기는 그 소화기가 위치한 방에서 K개의 통로 이내에 떨어져 있는 방까지 지킬 수 있다. 이를 소화기의 '영역'이라 하자.
- 각각의 방은 하나 이상의 소화기의 영역에 들어야 한다.
- 각 소화기는 최대 S개의 방을 영역으로 가질 수 있다.
Byteasar는 궁전을 짓느라 국고 대부분을 탕진한 상태다. 따라서 그는 궁전의 모든 방을 화재의 위험에서 벗어나도록 하는 소화기의 배치 중 최소 개수의 소화기가 배치되기를 원한다. Byteasar를 도와주자!
입력
표준 입력의 첫 줄은 N, S, K가 공백을 두고 입력된다. (1 ≤ N ≤ 100,000, 1 ≤ S ≤ N, 1 ≤ K ≤ 20) 다음으로 N-1줄 동안 두 개의 정수가 공백을 두고 입력된다. i+1번째 줄은 xi와 yi를 입력받는데, 이는 xi와 yi를 연결하는 간선이라는 뜻이다.
출력
필요한 최소 개수의 소화기를 출력하여라.
예제 입력 1
12 3 1 1 12 3 8 7 8 8 9 2 12 10 12 9 12 4 8 5 8 8 11 6 8
예제 출력 1
4
힌트
출처
Olympiad > Polish Olympiad in Informatics > POI 2008/2009 > Stage 1 1번
- 문제를 번역한 사람: jjwdi0
- 문제의 오타를 찾은 사람: kwanghyunon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호