2022. 7. 1. 15:24ㆍPS/Problem Solving
https://www.acmicpc.net/problem/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님의 글
'PS > Problem Solving' 카테고리의 다른 글
PS | 0710~0716 | 2022 (2) | 2022.07.10 |
---|---|
UCPC 2022 예선 (0) | 2022.07.03 |
Road to PS God (0) | 2022.06.24 |
Full Diamond (3) | 2021.06.11 |
Amazing CF 공부 리스트 (0) | 2021.06.05 |