29204번 - KSA에서 숨바꼭질 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 233 | 31 | 28 | 25.000% |
문제
KSA에는 $1$번부터 $N$번까지의 건물이 있고 두 건물 사이를 양방향으로 연결하는 $N-1$개의 통로가 있다. $i$번 통로는 $A_i$번 건물과 $B_i$번 건물을 연결하며 임의의 건물에서 다른 건물로 가는 경로가 항상 존재한다. 민찬이와 에릭은 여기서 숨바꼭질하고 있다. 민찬이가 술래고 $1$번부터 $N$번 건물 중 어딘가에 숨은 에릭을 찾아야 한다.
민찬이는 남몰래 에릭의 옷에 숨겨놓았던 위치 추적 장치의 도움을 받아 숨바꼭질에서 이기려고 한다. 이 위치 추적 장치는 다음과 같은 방법으로만 위치를 알려준다.
- 위치 추적 장치의 리모컨에 정수 $x$ $(1 \leq x \leq N)$를 입력하면 $x$번 건물에서부터 에릭이 숨어있는 건물까지 가기 위해 지나야 할 최소 통로 수를 화면에 띄워준다.
위치 추적 장치의 배터리가 얼마 남지 않았기 때문에 민찬이는 위치 추적 장치를 많이 사용할 수 없다. 다음 행동을 $k$번 해서 에릭이 숨어있는 건물을 알 수 있는 가장 작은 $k$를 구해보자.
- 어떤 수 $x$ $(1 \leq x \leq N)$를 선택해서 리모컨에 입력한 후, 리모컨에 띄워지는 수를 확인한다.
단, 민찬이는 다음 행동을 결정할 때, 그 전 행동들에서 얻은 정보를 사용할 수 있다.
입력
첫 번째 줄에 정수 $N$이 주어진다.
$i+1$번째 줄에 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq N-1)$
출력
에릭이 숨어있는 건물을 알기 위한 최소의 $k$를 출력한다.
제한
- $2 \leq N \leq 2000$
- $1 \leq A_i < B_i \leq N$ $(1 \leq i \leq N-1)$
- $1 \leq i < j \leq N$인 모든 $i$, $j$에 대해서 $i$번 건물과 $j$번 건물을 연결하는 경로가 존재
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $A_i = 1$ $(1 \leq i \leq N-1)$ |
| 2 | 44 | $N \leq 100$ |
| 3 | 49 | 추가 제약 조건 없음 |
예제 입력 1
3 1 2 1 3
예제 출력 1
1
리모컨에 $2$번을 입력해서 한 번 만에 에릭이 숨어있는 건물을 알 수 있다.
예제 입력 2
5 1 2 2 3 3 4 3 5
예제 출력 2
2
예제 입력 3
8 1 2 1 3 2 4 2 5 2 6 3 7 3 8
예제 출력 3
3
출처
School > 한국과학영재학교 > 2023 KSA Automata Summer Contest I번
- 문제를 만든 사람: mickeyjung
- 문제를 검수한 사람: cologne, dohoon, eric00513, flakepowders, gs20036, parkky, runnie0427, utilforever, yongwhan
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호