tree 1

* 틀린 내용이 있을 시 지적 부탁드립니다.

문제는 더블릿 15 tree에 있는 bridging입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/bridging/bridging.php?pname=bridging

1부터 순서대로 반대편단자와 연결시키고 교차하지 않고 연결이 가장 많이 되었을 때 단자의 수를 구하는 문제입니다.

각각의 단자와의 연결에 대한 입력이 있을 때마다 그 전까지의 경우 중 가장 연결이 많이 되었을 때의 값을 갖고 있어야 합니다.

각 단자를 단말노드로 구성한 이진트리를 구성합니다.

2의 배수 중 단말노드의 수를 넘는 최소값이 전체 단말노드의 수가 됩니다.

에제 문제 6 4 2 6 3 1 5를 예로 보겠습니다.

root 노드의 인덱스를 1로 보았을 때 단말 노드의 첫 번째 인덱스는 8이 됩니다.

그리고 들어온 값에 대한 단말 노드의 인덱스는 8+들어온 값-1이 됩니다.

이 두값의 트리를 타고 올라가며 같은 부모노드의 값이 이전 값의 최대치를 가지고 있도록 합니다.

그리고 그 최대치의 값+1을 들어온 값의 단말노드의 모든 부모노드가 가지도록 갱신합니다.

4가 들어오면 이 단말 노드와 첫 번째 단말노드의 공통 부모인 인덱스 2번 트리의 값이 0이므로 이값에서 +1을 해준 값을 4번 단말노드의 모든 부모노드가 가지도록 합니다.

2가 들어오면 첫 단말노드의 공통 부모인 4번 트리(단말 노드X)의 값이 0이므로 이 값에 +1을 해주어 2의 단말노드의 부모노드에 +1을 해준 값을 갱신합니다.

6이 들어오면 첫 단말노드와의 공통부모는 루트노드가 됩니다.  하지만 루트노드의 값을 최대치로 볼 경우 이 후 모든 갱신된 값을 전부 최대치로 보게 됩니다.  예를 들면 9번 단말노드의 최대치를 루트노드에 갱신하고 8번 단말노드의 경우를 계산할 때 루트노드의 값을 보고 9번 단말노드의 최대치값을 이용하게 됩니다.  9번 단말노드는 8번과 교차하게 되므로 이용하면 안됩니다.

6번이 들어왔을 땐 이전 값들에 의해 갱신이 된 유효한 이전 단말노드의 부모노드의 값만을 참조하도록 합니다.  

4번과 2번 단말노드에 의해 갱신된 최대값인 2번노드의 값이 최대값이므로 여기에 +1을 해준값을 이용합니다.

2번 노드는 4번 단말노드에의해 1의 값을 가지고 4번과 2번은 교차되기 때문에 2번 단말노드에 의해서도 1의값을 가지게 됩니다.

6번 단말노드는 이 두 값중 하나의 값을 이용하면 됩니다.

3이 들어오면 이전 유효 값인 1, 2의 부모노드의 값으로부터 계산합니다.

이 후 루트노드의 값을 출력하면 됩니다.