BOJ 17947 - 상남자 곽철용

BOJ 17947 - 상남자 곽철용

일단 $4N$개의 수 중, $2M+2$개의 수들을 제외한 것들을 모두 모아서 모두 $K$로 나눈다음 정렬한다.

정답은 최대 $M-1$ 이다.

이제 이걸 그리디하게 최대한 많이 곽철용의 차이보다 큰 차이가 나는 쌍의 개수로 묶어주면 된다.

정답률이 낮은 이유는 단순히 투포인터를 $l=r=0$ 부터 시작하여 되는것대로 모두 묶어주는 풀이가 너무 쉽게 떠오르기 때문인데, 이 풀이에는 반례가 존재한다.

올바른 풀이는 이 수들을 반으로 나눠서 왼쪽과 오른쪽 각각 작은것부터 보면서 투 포인터로 푸는 것이다.

불가능하면 $r$을 $r \coloneqq r+1$ 같이 해주며 진행하는 식이다.

절반으로 나눈 집합을 $A, B$ 라고 하자. 두 집합의 크기는 같다. $4N-2M-2$ 는 짝수이기 때문이다.

$A$에서 두 명을 매칭시켜줄 수 있다면 $B$에 있는 한 명과 매칭을 시켜줄 수 있다.

$A$에서 한 명과 $B$에서 한 명을 뽑았을 때 매칭시킬 수 없다면 $A$에서 다른 누군가를 뽑아도 항상 $B$에 있는 사람보다 작거나 같기 때문에 매칭시킬 수 없다.

$wlog. A$에 있는 두명을 매칭시키고 나머지는 모두 $(A,B)$로 매칭시켰을 때, 더 최적인 경우가 있다고 하자.

$B$에는 최소 한 명의 매칭되지 못한 사람이 있다. $\because A$에서 두 명이 서로 매칭되었기 때문에

그럼 $A$에서 더 큰 사람을 $B$의 그 사람으로 교체한다고 하자.

정답은 변하지 않았기 때문에 더 최적일 수 없다.

귀납적으로 사람 수를 증가시켜서 증명될 것 같다.