[BOJ] 13316번: std::정렬부터 시작하는 디버깅 생활

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


ordering의 조건이 몇 가지 있는데

- cmp(a,a) = false

- cmp(a,b) = true -> cmp(b,a) = false

- cmp(a,b) = true, cmp(b,c) = true -> cmp(a,c) = true. 마찬가지로 cmp(a,b) = false, cmp(b,c) = false -> cmp(a,c) = false

입니다.

그런데 해당 코드에서는 cmp( (1,2), (0,0) ) = false, cmp( (0,0), (1,1)) = false인데 cmp( (1,2), (1,1) ) = true이기 때문에 ordering이 올바르지 않고, 이로 인해 sort가 이상하게 작동합니다. 즉 (0,0)을 포함한 데이터들에 대해 오류가 생길 수 있습니다. (0,0)을 포함시켜 여러가지로 테스트하다보면 반례 데이터를 만들어낼 수 있습니다.


https://github.com/blisstoner/BOJ/blob/master/13316.txt

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11062번: Card Game  (0) 2018.07.14
[BOJ] 1315번: RPG  (0) 2018.07.14
[BOJ] 1572번: 중앙값  (0) 2018.07.14
[BOJ] 15824번: 너 봄에는 캡사이신이 맛있단다  (0) 2018.07.11
[BOJ] 1086번: 박성원  (6) 2018.07.11
[BOJ] 11102번: 발전소  (0) 2018.07.10
  Comments