메타인지 #1

이 글의 발단은 메타인지#0을 참고 바랍니다.
2021/03/06 - [Problem Solving/Road to PS GOD] - 메타인지 #0

현재 L=1, R=31 => mid = 16 => Platinum 5

Platinum 5 문제를 푼다.
문제를 맞은 사람 수 대로 정렬하고 위에서부터 안 푼 문제를 푼다.

첫 문제는 단절점이다.
이 기세를 모아서 단절선도 풀었다. 비슷한 유형의 문제이기에 이건 카운팅 안 함.

두 번째 문제는 소트다. 친구가 푸는 거 보고 따라 풀었는데, 생각보다 많이 절었다 .-. 
처음엔 그래프 문젠줄 알았지만, 길이가 n인 경로를 빠르게 찾을 수 없어 실패.
다음날 그냥 그리디적으로 고른 다음 반복적으로 시뮬레이션하면 쉽게 풀 수 있더라.
n이 좀 커져도 될 듯 multiset 쓰면 O(N lg N)에도 될 듯 하다.

세 번째 문제는 노트북의 주인을 찾아서이다. 
바로 이분매칭인게 보인다. 기억을 되새겨 혼자 구현했다.

처음 읽어본 세 문제를 모두 스스로 구현해 정답을 얻어냈다.

다음 티어 결정!
L = 16, R = 31 => mid = 23 => Diamond 3