helios13   4년 전

코드 구조는 이렇게 짜려고 했습니다.

예시기준으로 해보겠습니다.

ex - 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
  • sort() 정렬

   [[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]

  • 오른쪽 요소와 비교, i[0]이 더 작은데 i[1]이 더큰 경우 상위호환 되므로 제거

    [[1, 4], [3, 5], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]

  • 오른쪽 요소과 비교, i[0]과 (i+1)[0]이 같으면 i[1] 또는 (i+1)[1]중 더 큰 거  상위호환 되므로 삭제 (i[0] 과 i[1]이 같으면 무시)

     [[1, 4], [3, 5], [5, 7], [6, 10], [8, 11], [12, 14]]

  •   젤 앞 요소부터 하나하나 세리기

  이 방식으로 풀려고 했습니다. 질문에 있는 반례는 전부 통과 했는데, 3%에서 멈추다가 틀리는 것을 보아

  기본 로직자체가 잘못된건지... 너무 궁금해서 질문드립니다 읽어주셔서 감사합니다.

opop20207   4년 전

알고리즘은 그리디 알고리즘을 사용한다는 점에서 일치합니다.

하지만 문제는 이 로직을 실행하는 것보다 간단하게 풀립니다.

입력받은 배열에 어떠한 전처리 하나만 해주고 그리디하게 고르면 됩니다.

n번째 선택에서 가장 이득이 되게 하기 위해서는 n+1번째 선택의 폭을 최대화하는 것입니다.

이 선택을 위해 어떤 전처리를 해야할지 생각해보시는걸 추천드립니다.

helios13   4년 전

감사합니다. 아직 감은 안잡히지만, 다른 방법들을 더 동원해보아서 풀어보겠습니다.

조언해주셔서 감사합니다. 그리고 우연찮게 반례를 잡았네요.

 정렬 - [[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개 이상이 등장하면 오류가 나는 부분을 발견했습니다.

감사합니다!

opop20207   4년 전

통과하셔서 필요없으시겠지만 이 문제의 풀이의 핵심은 정렬에 있습니다.

정렬을 다르게 한다던가 하는 방식으로 풀이를 찾아보세요

helios13   4년 전

뒤에 기준으로 정렬해보니까 아주 쉽게 풀렸습니다.

회의시간이 정해져있고 그 안에서 최대한 많은 회의를 하는게 아니라, 회의개수가 정해져 있기에

첫 회의가 끝나는 시간이 관건인걸 이해했고 뒷정렬로 그리디하게 고르니 상당히 쉬웠다는걸 알았습니다

감사합니다

댓글을 작성하려면 로그인해야 합니다.