일단 이분 매칭으로 풀어도 풀리긴 하는데 시간이 매우 오래 걸리고... O(VE) 이므로 데이터가 빡빡하게 들어오면 시간초과가 날 것 같다.
일단 greedy... 생각을 많이, 신중하게 하고 확실한 근거를 가지고 해야 하는데 대충 짐작으로 짰더니 틀렸다. 그리고 한 동안 왜 틀렸는지도 전혀 깨닫지 못했다... (애초에 내가 푼 방법에 대한 명확한 근거가 없었으니...)
(a번, b번)을 sorting하되 a번을 기준으로 sorting하고 a값이 같은 경우 b를 기준으로 sorting해서 앞에서부터 하나씩 선택하는 식으로 했는데, 반례를 찾았다.
1 ->test case 개수
3 3 -> n, m
//a, b값
1 3
1 3
2 2
인 경우 이다. 생각해보면... 어렵다.
일단 드는 생각이... 그렇다면, b-a값이 작은 순으로 sorting을 해야하는 것인가?
몇몇 분의 코드를 봤는데 기억나는 코드가 b값을 기준으로 sorting하고, b값이 같으면 a값을 기준으로 sorting한 것 같은데... 이렇게 해도 되는 것인지 확실하게 입증을 못하겠다.
물론 b-a값이 작은 순으로 한다고 해서 맞는 것인지도 확실하게 증명은 못 하겠다.
일단 제출해 봐야겠다.... 틀렸다...
반례가 있는 것인가... 반례는 비교적 빨리 찾을 수 있었다.
n : 4, m : 4
//a, b값
1 1
2 2
1 3
3 4
인 경우이다. 일단 1 1, 2 2 인 경우를 먼저 처리하고 3 4를 처리할 때, 내 코드에서는 앞에 것을 먼저 선택하기 때문에 3을 선택하게 되고, 자연히 뒤에 오는 1 3을 처리할 때 아무 것도 선택할 수 없게된다.
그렇다고 뒤에서부터 선택하는 것은 해결책이 될 수 없다. 유사한 반례가 생긴다.
그리고 다른 분 코드를 봤는데,
b값을 기준으로 오름차순 sorting, b값이 같을 경우 a값 기준으로 내림차순 sorting...
일단 나중에 좀 더 공부하고 다시 풀어 봐야겟다...
댓글 없음:
댓글 쓰기