100 : The 3n+1 Problem

문제 : http://goo.gl/scOU

프로그래밍 챌린지 책을 보면서 새롭게 시작한 문제제공 및 Judge 서비스 해주는 곳이다. ACM ICPC와 매우 연관깊은 곳이기도 하다.

이 문제는 TLE에 유의해야한다.

힌트를 주자면 Memory cashing으로 Time, Space Trade-off하면 굉장히 빠른 시간에 답을 도출할 수 있다.
책을 자세히 읽어보지않아서 인풋을 while(scanf(...)==2) 이런식으로 받아야 하는 것을 몰라 한참 고민했다 ㅠㅠ..
- 주의 -
Recursion으로 구현했는데 FunctionCall StackOverFlow발생 :( ...
64bit integer 필요.


메모는 100만개짜리 int 배열.

while(scanf("%d %d",&a, &b)==2)
{
 int maxlen=0;
 int newA=a, newB=b;
 if(newA>newB) {newA=newA^newB; newB=newA^newB; newA=newA^newB;} // a,b swap

 for(int i=newA; i<=newB; i++)
 {
  cnt=1;
  int tmp;
  if( memo[i]==0)
   memo[i] = cycle_lenth(i);
  tmp = memo[i];
  if( tmp>maxlen) maxlen = tmp; // maxlen 갱신

 }
 printf("%d %d %d\n", a, b, maxlen);

}

int cycle_lenth(long long int n)
{
 long long int original = n;
 while(n!=1)
 {
  if(n<1000000)
   if(memo[n]!=0 )
   {
    cnt += (memo[n]-1);
  //  memo[original] = cnt;
    break;
   }

  if( n%2 ==0) //짝수
  {
   n /= 2;
   cnt++;
  }
  else //홀수
  {
   n = 3*n+1;
   cnt++;
  }
 }
 return cnt;
}