Informatica Online Judge

  Bad Hair Day III [2293 / 08F5]

Time Limit(Test case) : 500(ms)
Number of users who solved : 0   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JKJeong 2018]

Background

경곽이는 BHD(Bad Hair Day)문제의 해법을 이해한 후, 컴퓨터프로그래밍 시간에 Binary Tree에 대해서 배웠다.

특히 CBT(Complete Binary Tree)를 배열로 저장할 수 있다는 사실에 놀랐다.

경곽이는 이 BHD와 CBT의 아이디어를 종합하여 새로운 문제를 생각했다.

CBT의 경우 PreOrder Traverse, InOrder Traverse, PostOrder Traverse로 세 가지 순회 방법이 있고, 이 순회 순서에 따른 새로운 BHD문제에 대해 생각했다.

예를 들어 6마리의 소가 있고 각각의 키가

10, 3, 7, 4, 12, 2

인 경우 BHD의 값은 5이다. (자세한 설명은 200번 문제를 참고)

이 배열의 값을 CBT로 생각하면 다음과 같은 구조가 된다.

10
/ \
3 7
/ \ /
4 12 2



이 트리를 PreOrder Traverse한 결과는

10 3 4 12 7 2

가 되고 이 때 BHD값은 5이다.

다음으로 InOrder Traverse 한 결과는

4 3 12 10 2 7

이 되며 이 때 BHD값은 6이다.

마지막으로 PostOrder Traverse 한 결과는

4 12 3 2 7 10

이 되고, 이 때 BHD값은 5이다.

이와 같이 총 4가지의 BHD값을 구할 수 있고 이들의 총 합은 5+5+6+5 = 21이 된다.

이것만 구하는 것은 너무 쉽기 때문에 문제를 약간 어렵게 바꿔보자.

초기 배치에서 소 두마리의 위치를 최대 1번 바꿀 수 있다.
(인접하지 않은 소라도 관계없다.)

예를 들어

10 3 7 4 12 2

에서 3과 12의 위치를 바꿔보자.

그러면

10 12 7 4 3 2

이 때의 모든 BHD의 값을 구하면

원래 배열 : 10
PreOrder : 6
InOrder : 6
PostOrder : 4

이므로 10+6+6+4 = 26 이 된다.

26보다 더 큰 값이 나오도록 바꿀 수 있는 경우는 없으므로 구할 수 있는 최댓값은 26이다.

이와 같이 최대 한 쌍의 소 위치를 바꿀 수 있을 때 얻을 수 있는 최대 BHD의 합을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 소의 수를 나타내는 자연수 n이 입력된다.

두 번째 줄에 각 소들의 키가 공백으로 구분되어 입력된다.

[입력값의 정의역]

1 <=n<=1,000
각 소들의 키 <= 10^9

Output

최대 한 쌍의 소 위치를 바꿀 수 있을 때, 원래 배열, PreOrder, InOrder, PostOrder의 순회로 구한 모든 BHD의 총합 중 최댓값을 출력한다.

IO Example

입력
6
10 3 7 4 12 2

출력
26

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]