10068번 - 구슬이 서말이라도 꿰어야 보배 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 289 | 48 | 39 | 17.647% |
문제
요즘 고려대학교에서 가장 유행하는 게임은 "구슬을 꿰어라" 이다. 게임 이름에서 알 수 있듯이 이 게임은 구슬과 실을 이용해서 한다. 실은 총 두 가지 색상이 있고, 빨간색과 파란색이다. 구슬은 1번부터 n번가지 번호가 매겨져 있다. 게임은 구슬 1개를 가지고 시작한다. 이제 다음과 같은 과정을 통해 새로운 구슬을 실을 이용해 추가할 수 있다.
- Append(w, v): 새로운 구슬 w를 이미 가지고 있는 구슬 v에 빨간 실을 이용해 연결한다.
- Insert(w, u, v): 새로운 구슬 w를 이미 빨간 실로 연결된 구슬 u와 v사이에 파란 실 두 개를 이용해 연결한다. 이때, u와 v를 연결하는 빨간 실은 제거해야 한다. 즉, 이미 존재하는 빨간 실 u - v가 새로운 파란 실 두 개 u - w, w - v로 교체된다.
모든 실은 특정 길이를 가진다. 게임이 종료되었을 때, 최종 점수는 구슬을 연결하는 파란 실 길이의 합이다.
게임이 모두 종료된 상태가 주어진다. 상태는 실이 연결하고 있는 두 구슬의 번호와 길이로 이루어져 있으며, 색상은 알 수 없다.
문제에서 주어진 연결 상태를 만드는 방법은 여러 가지가 있다. 이때, 모든 방법 중에서 가장 큰 최종 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 구슬의 수 n이 주어진다. (1 ≤ n ≤ 200000) 구슬은 1번부터 n번가지 번호가 매겨져 있다. 다음 n-1개 줄에는 실의 정보 ai, bi, ci가 주어진다. (1 ≤ ai < bi ≤ n, 1 ≤ ci ≤ 10000) ai와 bi는 실이 연결하는 구슬의 번호이고, ci는 길이이다.
출력
가능한 점수 중에서 가장 큰 최종 점수를 출력한다.
예제 입력 1
5 1 2 10 1 3 40 1 4 15 1 5 20
예제 출력 1
60
힌트
예제의 경우에 아래와 같이 연결하면, 60점을 얻을 수 있다. 시작은 3번 구슬로 시작한다.
- 5와 3을 연결한다. (선의 길이는 상관없다)
- 1을 3-5 사이에 넣는다. (길이 40, 20 선을 이용)
- 2와 1을 길이가 10인 선을 이용해 연결한다.
- 4와 1을 길이가 15인 선으로 연결한다.
연결은 아래와 같아지고, 이 방법보다 더 큰 점수를 얻을 수 있는 방법은 없다.
출처
© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호