9576번 - 책 나눠주기
문제 분류는 매칭으로 되어 있지만 그리디도 성립한다고 생각합니다.
a순으로, a가 같다면 b 순으로 정렬한 후 그리디를 통해 풀었지만 틀린 답이라고 나옵니다 ㅠㅠ
반례가 있나요?
저는 정렬의 순서를 반대로해서 정답을 받았습니다.
모바일이라서 실행은 못하지만, 아마 이게 반례일 것 같습니다.
1 2
1 3
2 2
b, a 순서로 정렬해서 거꾸로 진행하면 이게 반례가 될 거 같은데, 의외네요.
2 3
n, m은 모두 3, 3으로 두었습니다.
제 코드에선 답이 3으로 잘 나옵니다.
그래도 제 코드가 정답인지 저도 확실치 않아서 제 코드를 올려봅니다.
다들 너무 감사드립니다 ㅠㅠ
제 알고리즘에 하자가 있는 것이었네요 ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
medic_programmer 6년 전 2
문제 분류는 매칭으로 되어 있지만 그리디도 성립한다고 생각합니다.
a순으로, a가 같다면 b 순으로 정렬한 후 그리디를 통해 풀었지만 틀린 답이라고 나옵니다 ㅠㅠ
반례가 있나요?