원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
산책로
원제: 산책로
문제
KOI 산에는 번부터 번까지 번호가 부여된 개의 쉼터가 있고, 그 쉼터들을 잇는 개의 양방향 산책로가 있다.
()번 쉼터에 사람이 얼마나 많은지를 나타내는 밀집도는 양의 정수 로 나타낼 수 있다.
()번째 산책로는 번 쉼터와 번 쉼터를 이으며 (), 그 길이는 이다. 즉, 쉼터들은 산책로를 통해 연결된 트리 구조를 이룬다.
고독한 산책가 교준이는 서로 다른 두 쉼터를 골라, 두 쉼터 사이의 유일한 단순 경로를 따라 산책하려고 한다. 어떤 경로를 선택했을 때,
- 경로에 포함된 산책로의 길이의 합을 ,
- 경로에 포함된 쉼터의 밀집도의 최댓값을
이라고 하자. 교준이는 산책을 길게, 그러나 사람이 적은 곳에서 고독하게 즐기고 싶기 때문에, 이 경로의 만족도는 으로 정의된다.
교준이가 산책할 경로의 만족도를 최대화하기 위해서는 어떤 두 쉼터를 골라야 하는지 계산하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 ()에 대하여
- 정수 ()에 대하여 이고
부분문제
- (8점)
- (12점)
- (11점)
- (15점) 정수 ()에 대하여
- (17점)
- (36점) 집합 에 등장하는 서로 다른 정수의 개수는 이하이다.
- (51점) 추가 제약 조건 없음.
입력 형식
첫 줄에 정수 이 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에 경로의 만족도가 최대가 되는 서로 다른 두 쉼터의 번호를 공백으로 구분하여 출력한다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
예제
예제 1
2 1 2 2 1
1 2
번 쉼터와 번 쉼터 사이의 경로의 만족도는 로 최대이다.
예제 2
4 6 10 20 1 2 4 4 3 21 15
1 3
가능한 모든 경로의 만족도는 다음과 같다.
- 경로 의 만족도는 .
- 경로 의 만족도는 .
- 경로 의 만족도는 .
- 경로 의 만족도는 .
- 경로 의 만족도는 .
- 경로 의 만족도는 .