180 Baking Cakes

  • 룡이
    룡이

    어째.. 여기서 문제 풀면서 노는 사람이 저 밖에 없는거 같아서 뻘줌하지만서도...
    180 Baking Cakes 질문 드립니다~!
    쉬운 문제 같은데.. 실행시간제한이 5000ms 인 것도 그렇고,
    랭크 리스트도 실행시간이 꽤 긴걸로 봐서 어려운 문제인가봐요..;;
    문제는 오븐이 세개고 케잌 다 구우면서 제일 짧게 걸리게 할 수 있는 시간이 얼마냐 인데요.
    예전에 스케쥴링 알고리즘 배울 때를 기억해 보면....
    놀고 있는 CPU 에 남은 작업 중 제일 실행시간이 긴 거를 넣으면 되는 거 같은데요.
    문제대로 케잌 굽는 시간이 6 7 8 9 10 걸린다 하면...
    오븐 세개 (A,B,C) 에
    A - 10
    B - 9 6
    C - 8 7
    순서대로 제일 길게 구워야 되는걸 넣고..
    끝난 애는 다시 남은 케잌 중에 제일 긴 시간이 필요한 걸 넣는 방식에..
    반례가 있나요 ?!?!!!
    데굴데굴 머리를 굴려봐도.. 반례가 없는거 같은데...
    0ms 에 Wrong Answer 나와서 좌절하고 있습니다 ;;
    도와주세요~

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    14년 전
2개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    네. 반례 있습니다.
    한 가지 반례 찾아봤는데, 접어둡니다.
    [spoiler="반례"] 케잌 굽는 시간이 5,5,4,4,3,3,3,3이 있는 경우를 생각합니다. 5,5 // 4,3,3 // 4,3,3 으로 배치하는 것이 최적임을 압니다. [/spoiler]


    14년 전 link
  • 장홍준
    장홍준

    사용할 수 있는 오븐이 3개가 있다는 점을 고려해 다이나믹으로 접근하시는게 편하실 것 같네요.


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.