[c++] 백준 #5000 빵정렬
정렬을 할 때마다 규칙성을 찾아야 하는 게 문제인데 나는 그걸 못 찾아서 친구의 풀이를 듣고 깨달음을 얻었다. 정렬을 할 때마다 역순 pair의 홀짝성이 유지가 된다는 것이 특징. 예를 들어 (4, 3, 2)는 (4, 3), (3, 2), (4, 2) 총 3개의 역순 pair를 가진다. 이를 빵정렬하면 (2, 4, 3)이 되는데 이거는 역순 pair를 (4, 3) 하나만 가진다. 그러면 역순 pair의 수가 홀수인 순열은 아무리 빵정렬을 해도 역순 pair의 수가 홀수개이다. 역순 pair 수가 짝수개가 죽어도 될 수 없다는 의미. 그러므로 주어진 두 input의 역순 pair 수를 세보고 둘다 짝수거나 둘다 홀수면 Possible, 아니면 Impossible을 띄우면 된다. 역순 pair를..
2019. 11. 5.