[editorial] 2008년 ACM ICPC 서울대회 인터넷 예선 H번 Homework

  • astein
    astein
    • Problem Statement s1, s2, ..., sN인 N명의 학생이 있다. si 학생은 어떤 숙제를 해결하기 위해 ti 만큼의 시간을 필요로 한다. 자신의 숙제를 끝낸 학생은 한시간에 한번씩 다른 학생한테 연락을 할 수 있다. 숙제가 나와 있다는 사실을 통보 받은 학생은 자신의 숙제를 끝낸 후, 다른 학생에게 연락을 취한다. Professor가 s1에게 새로운 숙제가 올라왔다는 사실을 알려주었다. 최대한 빠른 시간 내에 모든 학생들이 숙제를 제출하는 것을 목표로 할 때, 얼마만큼의 시간이 지나면 모든 학생들이 숙제를 완료할 수 있겠는가?
    • Analysis H번에 위치해 있고 문제가 영어였지만 , N <= 10이라는 것이 매우 중요한 포인트가 됩니다. 임의의 순열 1, a2, ..., an 이 있다고 합시다. 처음 위치에는 항상 1이 나오게 되는 것이, 교수는 1번 학생에게 연락을 하기 때문이지요. 1번학생은 자신의 숙제가 끝나면 a2번 학생에게 연락을 합니다. 또 1시간 후에 a3번 학생에게 연락을 합니다... 이 순서대로 연락을 취하면 언제 끝나는지 구할 수 있지요. (꼭 1번학생이 아니더라도 자신의 숙제가 끝났다면 순열에서 다음차례에 있는 학생에게 연락을 하면 됩니다.) 그러면 어떤 순열이 있을 때, 이 순열에 따라 연락을 취하면 걸리는 시간을 구할 수 있습니다. (일종의 시뮬레이션이지요) 이 순열을 최대 9! 가지의 경우가 존재하기 때문에 실행시간이 그렇게 오래 걸리진 않습니다. 'ㅅ' --- 요청이 들어와서 추가설명 들어갑니다. 시뮬레이션 하는 부분에 대한 요청이 들어왔네요. 코딩의 편의[?]를 위해 priority_queue를 사용하여 구현하였습니다. 숙제하는것/연락하는 것을 하나의 job으로 생각한다면, "어떤 학생이, 어떤 시점에 끝나는 Job을 가지고 있다"고 판단할 수 있지요. 또한 각 Job이 끝나면 다음 턴의 학생에게 연락을 취하는 상황이고요. 
    struct job   
{   
   int no; // student no   
   int endtime; // end time   
   bool isHomework; // TRUE라면 HOMEWORK를 하는 것이고, FALSE라면 연락을 하는 것입니다.   
   job (int a=0, int b=0, bool c=true) : no(a), endtime(b), isHomework(c) {}   
   bool operator < (const job &a) const { return endtime > a.endtime; }   
};   
// t는 시간을, p는 permutation을 의미합니다. p는 0 ~ n-1의 수로 이루어져 있고, 첫번째는 0이겠지요.   
int getTime(vector <int> t, vector <int> p)   
{   
   priority_queue <job> Q;   
   int maxTime = -1, turn = 1; // turn: i번째 학생에게 연락할 차례   
   Q.push(job(0, t[0], true));   
   while (!Q.empty())   
   {   
      job now = Q.top(); Q.pop();   
      if (now.isHomework) maxTime = max(maxTime, now.endtime);   
      if (turn != t.size())   
      {   
         Q.push(job(p[turn], now.endtime + t[p[turn]], true));   
         Q.push(job(now.no, now.endtime + 1, false));   
         turn++;   
      }   
   }   
   return maxTime;   
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
6개의 댓글이 있습니다.
  • soyoja
    soyoja

    이 문제가 어렵게 느껴진 것이, 1시간씩 시간이 흐름에 따라, 숙제를 다 끝낸 학생들이 아직 숙제를 받지 않은 학생들에게 숙제를 알려주는 과정을 모델링 해야 하는데, 이 부분을 코딩으로 옮기려니 상당히 복잡하더군요;; 시간을 1 시간 단위로 증가시키면서 ,현 시점에서 누가 숙제를 완료했고, 누가 숙제를 아직 받지 않았는지와 누가 숙제를 하고 있는지를 체크해야 하고, 또 숙제를 하고있는 학생은 숙제를 완료하는데 몇시간 남았는지도 정보를 갖고 있어야 하고.. 상당히 어렵게 느껴집니다 -0- 게다가 2 명 이상에게 숙제가 동시에 전달될 수도 있고 해서... -0-;;
    깔끔하게 구현할 수 있는 방법 없을까요? (Pseudo Code 라도 좀... )


    16년 전 link
  • astein
    astein

    본문에 추가하였습니다. :D


    16년 전 link
  • 하루
    하루

    이렇게 해도 Time Limit Exceed 안 나왔어? 나와야 하는데;;;
    아스탱, N이 무지 크면 어떻게 풀꺼야?(시비 아님 -_-;) 한번 생각해보라구.. ^_^


    16년 전 link
  • astein
    astein

    전 학생이 아니라서요 ㅇ<-< 그냥 외부인이니까요...
    제출해보고 싶은데 환경이 없어요 ;ㅁ;


    16년 전 link
  • astein
    astein

    근데 잠깐[?] 생각해 봤는데 어차피 Max Time을 Minimize 하는 문제이기 때문에, 1번 학생을 제외하고는 역순으로 정렬한 순서대로 연락하는게 나을 것 같네요. 흠...


    16년 전 link
  • JongMan
    JongMan

    당시 10! 에서는 TLE 가 나고, 9! 에서는 Yes 가 나왔다는 증언이 있습니다. -_-;;


    16년 전 link

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