12947번 - 트리 만들기

트리는 사이클이 없는 연결 그래프이다. 정점 N개로 이루어진 트리는 N-1개의 간선으로 이루어져 있다.

트리의 두 정점 사이의 거리는 한 정점에서 다른 정점으로 갈 때, 지나는 간선 개수의 최솟값이다.

트리의 지름은 모든 두 정점 사이의 거리 중에서 가장 큰 값이다.

아래와 같은 조건을 만족하는 트리 중에서 지름이 가장 긴 것을 만들어보자.

• 트리의 루트를 V라고 하자.
• V에서 가장 거리가 먼 정점과의 거리를 D라고 하자.
• 1보다 크거나 같고, D보다 작거나 같은 모든 i에 대해서, 거리가 i인 정점의 개수는 cnt[i] 이다.

cnt배열이 주어졌을 때, 만들 수 있는 트리 중에서 지름이 가장 큰 것의 지름을 출력하는 프로그램을 작성하시오.

첫째 줄에 cnt 배열의 크기 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에는 cnt 배열의 값이 cnt[1]부터 cnt[N]까지 차례대로 주어진다. (1 ≤ cnt[i] ≤ 1000)

첫째 줄에 문제의 조건을 만족시키는 트리 중에서 지름이 가장 큰 것의 지름을 출력한다.

예제 1의 경우에 만들 수 있는 트리는 한 가지이다.

예제 2의 경우에 다음과 같은 두 가지 트리를 만들 수 있다. 왼쪽 트리의 지름은 3, 오른쪽 트리의 지름은 4이다.

예제 3의 경우에는 아래 그림과 같은 트리를 만들 수 있다.