1700번 - 멀티탭 스케줄링
질문게시판의 댓글에 있는 반례들은 전부 해 보았고, 통과하는 것을 확인했습니다.
어디서 틀리는지 반례를 찾다가 아래 예제를 찾았습니다.
2 4
5 3 1 5
문제에 주어진 대로 가장 늦게 쓸 기기를 뽑고 꽂는다면
1) 멀티탭에 5번 3번 꽂음
2) 가장 늦게 쓸 기기(5번)을 뽑고 거기에 1번을 꽂음. 현재는 1번, 3번 꽂혀있음.
3) 가장 늦게 쓸 기기(3번)을 뽑고 거기에 5번을 꽂음.
==> 답: 2.
하지만 위의 2) 단계에서 3번을 뽑고 1번을 꽂게되는 것이 최적으로, 답은 1이어야 합니다.
현재 첨부된 제 코드에서도 답이 2로 나오고 문제대로 그리디 알고리즘에 맞게 풀었다고 생각하는데...
제가 문제를 잘못 이해한건지 설명부탁드립니다 ㅠㅠ
2에서 가장 늦게 쓸 기기는 3번이죠. 3번은 안쓸거니깐. 이 처리를 해야겠네요.
아예 안 쓸 기기에 대한 처리를 빼먹었군요 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
chsun0303 5년 전
질문게시판의 댓글에 있는 반례들은 전부 해 보았고, 통과하는 것을 확인했습니다.
어디서 틀리는지 반례를 찾다가 아래 예제를 찾았습니다.
2 4
5 3 1 5
문제에 주어진 대로 가장 늦게 쓸 기기를 뽑고 꽂는다면
1) 멀티탭에 5번 3번 꽂음
2) 가장 늦게 쓸 기기(5번)을 뽑고 거기에 1번을 꽂음. 현재는 1번, 3번 꽂혀있음.
3) 가장 늦게 쓸 기기(3번)을 뽑고 거기에 5번을 꽂음.
==> 답: 2.
하지만 위의 2) 단계에서 3번을 뽑고 1번을 꽂게되는 것이 최적으로, 답은 1이어야 합니다.
현재 첨부된 제 코드에서도 답이 2로 나오고 문제대로 그리디 알고리즘에 맞게 풀었다고 생각하는데...
제가 문제를 잘못 이해한건지 설명부탁드립니다 ㅠㅠ