Google code jam 2010 Qualification Round : Problem C

Problem :  http://code.google.com/codejam/contest/dashboard?c=433101#s=p2


B번 문제에서 그렇게 해석에 애먹고 고생해서 그런지, 이번문제는 5분만에 읽고 해석 및 solution이 떠올랐다. 하지만, 세상에 쉬운일이 없듯이 이번 문제는 [효율]의 문제다.
그리고 또다시 부상한 Big Integer Class -_-+...


접근방법
문제를 읽은 후 사고의 흐름은 이렇다.
1. 배열로 그룹잡고 줄 빠지면 빼서 뒤로 넣고, 빼서 뒤로 넣고 하면되겠네.. 그런데 너무 삽질 같다?

2. 아, 그럼 STL의 위엄을 발휘해서 List로 하면 pop(), pushback()하면 편하겠다. 이렇게 해볼까?

3. 가만... 이거 1번 Riding할때마다 이렇게 수정해버리면 Overhead가 심해서 Complexity가 너무 올라가는데?.;;;

4. 아! 각 위치마다 시작지점과 버는 돈을 Hash Table로 만들어서 참조만 하면 효율이 확 올라가겠다!

5. 구축해놓고 참조만 할거니까, 컴퓨터적으로 조금 더 빠른 Array 2개를 이용하자!!

// next, earn 동적 배열을 채우는 루틴
  for(int i=0; i<numOfGroup; i++)
  {
   int sum=0;
   // cnt는 모두 태우고 남는 경우를 처리해주기 위함.
   for(int j=i, cnt=0; ; j++, cnt++)
   {
    if( j== numOfGroup) j=0;
    if( sum+group[j] <= canBoard && cnt!=numOfGroup)
    {
     sum += group[j];
    }
    else
    {
     next[i] = j;
     earn[i] = sum;
     break;
    }
   }
  }
 
  // solution 도출
  int forward=0;
  for(int i=0; i<numOfRide ; i++)
  {
   income += earn[forward];
   forward = next[forward];
  }