cjkim2002   1년 전

로컬에서 여러 테스트 케이스를 만들었을 때 문제 없이 작동해서 제출하니 2%에서 틀렸다고 바로 나옵니다.

어느 부분에서 잘못 되었는지 궁금합니다.

강의실 개수를 배정하기 위해 하나의 강의실에서 최대한 많은 가능한 강의실을 배치한 후 ans += 1을 통해 강의실 개수를 업데이트하는 방식을 사용했습니다.

pos의 경우 T를 기준으로 vector을 오름차순으로 정렬했기 때문에 조건에 처음으로 부합하지 않은 index를 다음 loop의 pos로 업데이트 했습니다.

adfsfsf   1년 전

반례 드리겠습니다.
예시는 가장 아래에, 코드 창에 있습니다.

제가 적은 예시를 기준으로 따라가보겠습니다.

28~30줄에서 정렬된 후의 결과는 다음과 같습니다.

1 2
2 3
2 4
4 5

이제 36번 줄에서 시작되는 while문을 따라가보겠습니다.

current_start는 1, current_end는 2입니다.

43번 줄의 for문에서 i는 1부터 시작합니다.
45번 줄의 조건이 참이므로 visited[1]은 true가 되며, cnt가 2가 됩니다.
50번 줄의 조건은 거짓이므로 for문 처음으로 돌아갑니다.
문제는, 여기서 'current_end가 2인 상태가 유지'되었다는 것입니다.
'한 강의실에 최대한 많이 넣는다'는 조건대로라면, '1->2'인 강의가 끝난 강의실에 '2->3' 강의를 할당했을 때 다음부터는 시작 시간이 3 이상인 강의만 더 넣을 수 있습니다.
그렇지 않고 2를 유지해서 '2->4'인 강의가 수용되었습니다.
따라서 출력이 1이 되었습니다.

adfsfsf   1년 전

추가로 보충 설명을 하자면, 지금의 이중 루프 형식으로는 그 문제를 해결하셔도 시간 초과가 발생합니다. 다른 글에서 언급되는 우선순위 큐를 활용해서 풀어야 합니다.

cjkim2002   1년 전

오, 감사합니다!

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