그냥 하는 노트와 메모장

* CS Academy Round #9 - Array Removal[ 분류 - DSU ] 이 문제의 특성은 다음과 같다. 1. 지워야하는 순서가 정해져 있다. 2. 순서가 정해져 있는 만큼, k 번째 수를 지웠을 때 큰 수 S_k와 k+1번째 수를 지웠을 때 큰 수 S_k+1는 서로 종속적이다. 3. 수를 제거해나가며 큰 수를 출력해야 한다. 먼저 Greedy하게 접근해보자. S_k와 S_k+1를 비교해보자면 S_k >= S_k+1이 성립함을 직관적으로 알 수 있다. 또한 2.번에 의해 서로 종속적이기 때문에, "순서를 거꾸로" 생각하자. 거꾸로 생각하면, 초기에 없는 데이터에서 하나씩 생성됨을 알 수 있다. 따라서 이를 DSU로 합치는 방식을 택하며, 지금 합친 것과 지금까지의 최대값을 비교해나가며 답..