알고리즘은 그리디 알고리즘을 사용한다는 점에서 일치합니다.
하지만 문제는 이 로직을 실행하는 것보다 간단하게 풀립니다.
입력받은 배열에 어떠한 전처리 하나만 해주고 그리디하게 고르면 됩니다.
n번째 선택에서 가장 이득이 되게 하기 위해서는 n+1번째 선택의 폭을 최대화하는 것입니다.
이 선택을 위해 어떤 전처리를 해야할지 생각해보시는걸 추천드립니다.
1931번 - 회의실 배정
감사합니다. 아직 감은 안잡히지만, 다른 방법들을 더 동원해보아서 풀어보겠습니다.
조언해주셔서 감사합니다. 그리고 우연찮게 반례를 잡았네요.
정렬 - [[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [9, 9], [9, 9], [9, 9], [12, 14]]
1차삭제 - [[2, 13], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [9, 9], [9, 9], [9, 9], [12, 14]]
2차삭제 - [[5, 7], [6, 10], [9, 9], [9, 9], [9, 9], [12, 14]]
제가 다음요소보다 i[0]값이 작은데 i[1]값이 더 크다면, 하위호환이라 생각되어 처리했는데,
하위호환이 연속될 때 젤 뒤에 있는 하위호환값 1차, 2차에서만 삭제가 되서 완전 하위호환 3개 이상이 등장하면 오류가 나는 부분을 발견했습니다.
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
helios13 4년 전
코드 구조는 이렇게 짜려고 했습니다.
예시기준으로 해보겠습니다.
ex -
[[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]
[[1, 4], [3, 5], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]
[[1, 4], [3, 5], [5, 7], [6, 10], [8, 11], [12, 14]]
이 방식으로 풀려고 했습니다. 질문에 있는 반례는 전부 통과 했는데, 3%에서 멈추다가 틀리는 것을 보아
기본 로직자체가 잘못된건지... 너무 궁금해서 질문드립니다 읽어주셔서 감사합니다.