wnsgur1595   10달 전

UCPC 2019 예선 C번문제인데, 그리디 알고리즘으로 풀려고 했어요.

일단, ms와 ms2라는 멀티셋 2개를 만들었고, ms는 모든 대회가 일찍 끝나는 순으로 정렬된 멀티셋이고, ms2는 K-1명이 마지막으로 참가한 대회의 끝나는 날(K-1개)들을 저장해놨습니다. 그래서, 처음에는 ms에서 맨앞부터 K-1개를 꺼내어 ms2에 끝나는날 K-1개를 채워넣구요. 그 다음부터는 형섭이가 끝나는날을 보면서 형섭이가 끝나는날 이전에 시작하는 대회는 ms에서 하나씩 삭제해나가고, 만약 형섭이가 대회에 참가할 수 있다면, 먼저 ms2의 K-1명도 참여할 수 있는지 먼저 확인한 후에, 참여할 수 있는 사람들 중 가장 마지막에 끝난 사람이 새로운 대회에 참가하도록 하였습니다.

제 코드에서 어떤 부분이 잘못된 걸까요..?

evenharder   10달 전

'가장 일찍 끝나는 대회 K-1개를 ms2에 저장한다.' 부분이 틀렸습니다.

가장 먼저 일찍 끝나는 K-1개의 대회들을 형섭이가 참가할 수 없는 건 맞지만, 경우에 따라서 K-1명보다 적은 인원으로도 이 대회들을 참가할 수 있기 때문입니다.

다음은 반례입니다.

wnsgur1595   10달 전

감사합니다ㅠㅠㅠ 전혀 생각하지 못한 곳에서 논리오류가 있었네요! 감사합니다ㅠㅠ

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