백준 16193 차이를 최대로, 백준 20131 트리 만들기

16193

문제에서 주어지는 식은 자주 다뤄진다.

내림차순이든, 오름차순이든 Ai~Aj(j>i)까지 정렬됐다면, 정리하면 ai,aj말고 다 지워진다.

내림차순이면 Ai - Aj일 것이고, 오름차순이면 Aj-Ai일 것이다.

만약, 정렬이 안돼있고 큰숫자,작은숫자,큰숫자...이 꼴로 반복된다면

Ai - Ai+1 + Ai+2 - Ai+1 + Ai+2 - Ai+3 .... 이 꼴이 된다.

i~j구간길이가 짝수라고 가정하면 Ai - Aj - 2(Ai+1 + Ai+3 + Ai+5 +....) + 2(Ai+2 + Ai+4 + Ai+6 + ..)로 정리 가능하다.

정렬이 안돼있는 것의 결과가 더 크다.

왜냐하면 Ai~Aj에서 최대를 M,최소를 m이라하면 전자는 M - m이되고, 후자는 2M - 2m + (나머지, 나머지 > 0)이기 때문이다.

위 식을 제일 크게만드려면, 큰것들은 2배를 해줘야하고, 작은것들도 -2배를 해준 결과가 돼야한다.

큰것 - 작은것보다 2*(큰것 - 작은것)이 더 크기 때문이다.

그렇게 정리하면 남는 ai - aj는 크기가 중간인 두 값이 될 것이다.

우선 A를 정렬하자.

1. N이 짝수

A[N//2-1],A[N//2]가 중간값이다.

A[0] ~ A[N//2-2]는 작은 값이다.

A[N//2+1] ~ A[N-1]은 큰 값이다.

2.N이 홀수

위에서 우리는 Ai>Ai+1 Ai+2>Ai+1 ...꼴만을 생각해봤다. 반대케이스인 Ai<Ai+1 Ai+2<Ai+1 ...꼴도 생각해봐야한다.

왜냐하면 N이 홀수일땐 Ai - Aj - 2(Ai+1 + Ai+3 + Ai+5 +....) + 2(Ai+2 + Ai+4 + Ai+6 + ..)는 조건을 뭘로 잡냐에 따라

2를 곱해주는 수들의 개수와 -2를 곱해주는 수들의 개수가 달라진다.

Ai>Ai+1 Ai+2>Ai+1 ...꼴이라면 수를 짝수케이스와 똑같이 수들을 분할해주면 된다.

Ai<Ai+1 Ai+2<Ai+1 ...꼴이라면 분할하는 것들이 달라진다.

A[N//2],A[N//2+1]이 중간값이다.

A[0]~A[N//2-1]이 작은값이다.

A[N//2+2] ~ A[N-1]이 큰 값이다.

두 케이스 모두 수열을 만들어보고 그중 큰 것을 취해준다.

 

 

20131

문제의 의미를 생각해보자.

차수가 1이라는 것은 그래프에서 트리의 리프노드 역할을 하는 무언가이다.(루트가 정해져있다는 말이 없으므로...루트를 1로 잡아도 1이 지워질 수 있다. 그래도 편하게 리프노드라고 하겠다.)

따라서 인접한 정점은 유일해진다.

a[i]의 의미는 해당 인덱스에서 선택한 리프노드와 인접한 부모가 a[i]라는 것이다.

수열 a에서 등장하지 않은 노드들은 리프노드들이다.

 같은 논리로, ak~aN-2에서 등장하지 않은 노드는 인덱스 k부터 리프노드가 된다는 것이다.

이제 우리가 필요한 것이 하나 정해졌다.

1. 각 노드들이 a에서 마지막으로 등장한 시점과 아예 안나왔는지를 알려주는 배열 maxidx

노드들은 수가 큰 순서대로 지워진다.

문제에서 말한 과정을 거치면서 a에서 아예 안나온 노드뿐만 아니라 새로운 리프노드들이 계속 생길것이다.

삽입도 logN이고 제일 큰 것도 logN만에 알아볼 수 있는 자료구조가 있다.

바로 우선순위 큐이다. 우선순위는 노드번호가 큰 순서로 두자.

2. 노드가 큰 우선순위로 담는 pq

이제 필요한 것들이 전부 만들어졌다.

1번을 만들면서 pq를 초기화해주자.

a를 순회하면서

만약 순회하고있는 idx가 maxidx[node]보다 커진다면 node를 pq에 삽입해준다.

나같은 경우엔 a에서 등장한 노드들에 대해 (maxidx[node],node)를 오름차순으로 정렬한 큐를 사용했다. 

pq를 pop해주고, pop해줘서 나온 결과는 a[idx]의 자식이므로 해당간선을 추가해준다.

출력을 조건에 맞게 해야하므로 간선들을 정렬해준다.

O(NlogN)에 해결가능하다.