#5402

트리 높이 줄이기

아래 그림에는 트리가 있다. 트리는 정점들과 간선들로 이루어진 구조이다. 간선은 정점들을 부모-자식 관계로 연결하고 있다. 위쪽에 있는 정점은 부모, 아래쪽에 있는 정점은 자식이라고 부른다. 어떤 정점의 자식도 아닌 정점을 루트, 어떤 정점의 부모도 아닌 정점을 리프라고 부른다. 트리의 높이란 루트에서 리프까지의 경로 위 간선 길이의 합 중 최댓값을 뜻한다.

정점은 원으로 표시되어 있고, 각 간선 옆에는 해당 간선의 길이가 나타나 있다. 루트 정점은 빨간 윤곽선으로, 리프 정점은 파란 윤곽선으로 강조되어 있다.

간선을 클릭한 다음 아래의 ▼ 버튼을 클릭하면 해당 간선의 길이를 1만큼 줄일 수 있으며, 초기화 버튼을 클릭하면 지금까지 줄인 이 간선의 길이를 초기화할 수 있다. 길이를 1만큼 줄이는 데에는 비용 1이 발생하며, 길이는 최소 1까지 줄일 수 있다. 간선의 길이는 실제 화면에 표시된 선의 길이와는 무관함에 유의하라. 화면의 상단에는 지금까지 사용한 비용이 표시되어 있다.

간선의 길이를 적절히 줄여 트리의 높이가 10 이하가 되도록 만들어야 한다. 또한, 길이를 줄이는 데에 드는 비용 또한 최소화하여야 한다.

채점 기준

트리의 높이가 10 이하이고, 비용이 가능한 최소 비용이면 전체 점수의 100%를 얻는다.

문제 해결이 끝난 후 반드시 ‘제출’ 버튼을 눌러 제출해 주세요.
문제를 해결하려면 로그인해 주세요.

문제 형식

    인터랙티브

출처

  • KOI 2025 1차대회 고등부 1교시 13번
  • KOI 2025 1차대회 중등부 1교시 14번
  • KOI 2025 1차대회 초등부 1교시 15번
연습하기도전하기함께하기보고 배우기
공지사항 · 이용안내
회원가입로그인
연습하기도전하기함께하기보고 배우기공지사항 · 이용안내