Strict Weak Ordering?

https://www.acmicpc.net/problem/16496 

16496번: 큰 수 만들기

이 문제는 Exchange Arguments의 전략을 쉽게 발상할 수 있는데, (문자열 A,B에 대해 AB>BA?)

인접한 것끼리만 교환한다고 생각하면
AB > BA 일 경우
X AB Y > X BA Y 이기 때문에 인접한 걸 계속 이득이 되도록 교환해나가면 최종적으로 가장 이득인 상태가 되는 것을 알 수 있다.
이는 결국 버블정렬을 시행하는 것과 같은데 N log N sort를 해도 같을 것이라는 가정을 하고 문제를 푼다. 

여기서 한가지 찜찜한 것이 이를 stl sort로 수행했을 때 정말 정렬이 잘 수행되냐는 것이다.

예를 들어 A<B , B<C일 때 정말 A<C가 맞는지,, 그런 조건이 있는지에 대한 의문이 계속들었었는데 역시 나타내는 말이 있더라. 바로 Strict Weak Ordering

https://panty.run/strict-weak-ordering/

결론만 가져오면

1,2는 어쩌면 당연한것이고 중요한건 3인데 정렬함수를 짤 때 이를 증명해야 문제를 정말 제대로 풀었다고 할 수 있을 것이다.

4번째 조건이 참, 이런게 있어야 되나 싶기도 한데 해석해보면 동등성과 같다고 한다.

x==y 이고 y==z이면 x==z 라는 뜻

저 문제에서 3번째 조건을 한번 증명해보자. (추이성)

a. AB> BA이고 b. BC>CB면
AC > CA 임을 증명해야 함.

121 1211

1211121

증명 너무 어려운데?

 

2023/01/22 UPD: https://www.acmicpc.net/board/view/96132 jh05013님의 글