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로 나오고 문제대로 그리디 알고리즘에 맞게 풀었다고 생각하는데...

제가 문제를 잘못 이해한건지 설명부탁드립니다 ㅠㅠ


startlink   5년 전

2에서 가장 늦게 쓸 기기는 3번이죠. 3번은 안쓸거니깐. 이 처리를 해야겠네요.

chsun0303   5년 전

아예 안 쓸 기기에 대한 처리를 빼먹었군요 감사합니다.

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