[JAVA|UVa] 100 3n+1 콜라츠

UVa 에 억셉트 되는 거는 문제풀이 알고리즘을 생각하는 것보다 훨씬 미묘한 문제를 많이 풀어야 한다. 알고리즘은 벌써 생각해서 풀었는데, 문제의 출력의 조건을 간과해서 한 10번은 빠꾸 맞았다. 접속은 또 잘 안 되지...

후왕.

캐싱을 해 놓는다른 건데, 한번 계산하면서 거쳐갔던 숫자들에까지 캐싱을 해 주어서 조금 더 빨리 해보려고 했다. 더 빨랐는지는 잘 모르겠다.

import java.util.*;

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

/*
 * 1 10
 * 100 200
 * 201 210
 * 900 1000
 */

public class Main {

   private static int MAX = 1000000;
   private static int cycle[] = new int[MAX];
   
   public static void main(String[] args) {
       
       int m, M, i1, i2;

       Scanner scnr = new Scanner(System.in);

       for(int i = 0 ; i<MAX ; i++) {
           cycle[i] = 0;
       }

       cycle[1] = 1;

       while(scnr.hasNextLine())
       {
           try {
               i1 = scnr.nextInt();
           } catch(Exception e) {
               break;
           }
           i2 = scnr.nextInt();

           if(i1 > i2) {
               M = i1;
               m = i2;
           } else {
               M = i2;
               m = i1;
           }

           System.out.println(i1 + " " + i2 + " " + getMaxCollatzCycle(m, M));

       }
   
   }

   public static int getMaxCollatzCycle(int m, int M) {
       int max = 0, cnt = 0;
       for(int i = m; i<=M; i++) {
           cnt = nCollatz1(i);
           //if(cnt != nCollatz1(i))
           //1  System.out.println("!!!!" + i);
           if(max < cnt) {
               max = cnt;
           }
       }
       return max;
   }

   public static int nCollatz(long n) {
       int cnt = 0;
       List<Long> v = new ArrayList<Long>();
       
       while(true) {
           //System.out.print(n + " ");
           if(n < MAX && cycle[(int)n] != 0)
               break;
           v.add(n);
           
           if(n%2 != 0) {
               n = n*3+1;
           } else {
               n /= 2;
           }
       }

       cnt = cycle[(int)n];
       cnt += v.size();

       for(Long m: v) {
           if(m < MAX) {
               long mm = m;
               cycle[(int)mm] = cnt;
           }
           cnt--;
       }
       
       return cnt + v.size();
   }

   public static int nCollatz1(long n) {
       int cnt = 1;
       
       while(n != 1) {
           if(n%2 != 0) {
               n = n*3 + 1;
           } else {
               n /= 2;
           }
           cnt+=1;
       }
       
       return cnt;
   }

}