Ugly Numbers/이동현

No older revisions available

UglyNumbers 소감 ¶

처음엔 어글리넘버의 규칙성을 찾았다. 이것으로 너무나 많은 시간을 허비하고나서
규칙성은 없다(실제로 없는지는 모름)고 결론.(있었다면 0.1초내로 답이 튀어 나올것이므로 '4초내로'라는 단서도 없었을듯..)
일단 n번째 어글리넘버 이후의 수들은 이전 어글리넘버에 2나 3이나 5를 곱해서 이루어진다는 것을 가지고 1부터 시작하여
n번째 수 까지 각각 2,3,5를 곱해나간다.

한가지 이상한점은 10만번째 어글리넘버가 44314690598262522787512975360 이 나오든데
문제에서 제시한 값과 너무 큰 차이가 나는듯.. 어디가 잘못되었는지 모르겠다.

소스 ¶

~cpp 
/*
 * Created on 2005. 3. 30
 */
/**
 * @author 중앙대 컴퓨터공학과 01 이동현
 */
import java.util.*;
import java.math.*;

public class UglyNumbers {
    public ArrayList arr;
    /**
     * n을 arr에 삽입하되 중복값이 있으면 아무것도 하지않아.
     * @param n double 삽입할 값
     * @return int 코드 1:삽입완료 -1:이미 값 있음 1:맨 마지막에 추가
     */
    public int insert(double n) {
        for (int i = 0; i < arr.size(); i++) {
            if (((Double) arr.get(i)).doubleValue() > n) {
                arr.add(i, new Double(n));
                return 1;
            } else if (((Double) arr.get(i)).doubleValue() == n)
                return -1;
        }
        arr.add(new Double(n));
        return 0;
    }

    public int start() {
        int index = 1;
        arr = new ArrayList();
        arr.add(new Double(1.0));
        while (index != 1500) {
            insert(((Double) arr.get(0)).doubleValue() * 2.0);
            insert(((Double) arr.get(0)).doubleValue() * 3.0);
            insert(((Double) arr.get(0)).doubleValue() * 5.0);
            arr.remove(0);
            index++;
        }
        System.out.println("The 1500'th ugly number is "+new BigDecimal(((Double)arr.get(0)).doubleValue()));// + " " + arr.size());
        return 0;
    }

    public static void main(String[] args) {
        UglyNumbers ug = new UglyNumbers();
        ug.start();
    }
}