프로젝트 오일러 :: 05번 문제풀이 :: java

문제

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

연구

이 문제는 1부터 20까지 모든 숫자의 최소공배수를 구하는 문제다.

분명 수학적 원리를 통해 이를 구하는 공식이 있겠지만, 그러한 공식을 검색하며 푸는건 마치 반칙을 저지르는 기분이므로 필자는 노트와 팬을 꺼내 규칙을 찾아보기로 했다.

1~10의 최소 공배수가 2520 임을 알고있으므로 이를 토대로 분석해본 결과,

작은 수부터 1을 제외한 어떠한 공약수가 없을 때 까지 소수로 전체 숫자를 나눈 남은 모든 숫자의 곱이 최소공배수이다.

위와 같은 결론을 도출할 수 있었다.

글로만 봐서는 잘 이해가 되지 않을 수 있기 때문에 그림과 함께 조금 더 설명을 들어보자.

위 그림은 1부터 10까지의 숫자를 모두 소인수 분해한 그림이며, LCM(Lowest Common Multiple)은 최소공배수를 뜻한다.

가장 작은 숫자인 1은 제외하고 2부터 전체 숫자와 나누어가보자.

1은 곱하는게 의미가 없기 때문에 제외하고, 나눈 숫자는 LCM에 추가후 배경색을 달리해서 표시하겠다.

0123456

이렇게 나누어 떨어지는 수는 나누고, 그렇지 않은 수는 곱해주면 최소 공배수를 구할 수 있게 된다.

이제 규칙을 찾았으니 컴퓨터가 이해할 수 있는 코드로 구현하면 된다.

풀이

우선 위에 사진으로 표현한 것 처럼 1부터 20까지의 숫자를 모두 소인수분해한 뒤 list에 저장해보자.

int MAX_NUMBER = 20;

void solution() {

     ArrayList<ArrayList<Integer>> listData = new ArrayList<ArrayList<Integer>>();

     /* step1. 2부터 20까지의 숫자를 소인수분해 */

     for (int i = 2; i < MAX_NUMBER + 1; i++)

           listData.add(factorization(i));

}

여기서 factorization이라는 함수는 class 안에 정의한 함수로 아래와 같다.

/**

 * 입력된 숫자를 인수분해 하여 반환한다.

 * @param arg 인수분해할 숫자

 * @return 인수분해 결과가 들어있는 ArrayList

 */

private ArrayList<Integer> factorization(int arg) {

     ArrayList<Integer> list = new ArrayList<Integer>();

     while (true) {

           if (isSosu(arg)) {

                list.add(arg);

                break;

           }

           for (int i = 2; i < arg; i++) {

                if (arg % i == 0) {

                     list.add(i);

                     arg /= i;

                     break;

                }

           }

     }

     return list;

}

/**

 * 입력된 숫자가 소수인지 아닌지를 구분해준다.

 * @param x 소수인지 여부를 파악할 숫자

 * @return 소수라면 true를, 아니라면 false.

 */

private boolean isSosu(long x) {

     boolean isSosu = true;

     if (x == 1 || x == 2)

           return true;

     for (long i = 2; i < x; i++) {

           if (x % i == 0) {

                isSosu = false;

                break;

           }

     }

     return isSosu;

}

소인수 분해가 끝났으니 연구 파트에서 설명한 것 처럼 2부터 20까지 1씩 증가시키며 공통 인수를 모두 지운 뒤에 남은 숫자만 곱하면 답이 나온다.

int MAX_NUMBER = 20;

void solution() {

     ArrayList<ArrayList<Integer>> listData = new ArrayList<ArrayList<Integer>>();

     /* step1. 2부터 20까지의 숫자를 소인수분해 */

     for (int i = 2; i < MAX_NUMBER + 1; i++)

           listData.add(factorization(i));

     /* step2. 숫자 n의 공약수가 x와 나누어 떨어지는 경우, 해당 숫자를 지워준다. (단, x > n) */

     ArrayList<Integer> listMinNum, listCompareNum;

     int tmp;

     for (int idxData = 0; idxData < listData.size(); idxData++) {

           listMinNum = (ArrayList<Integer>) listData.get(idxData);

           if (listMinNum.isEmpty())

                continue;

           for (int idxCompareData = idxData + 1; idxCompareData < listData.size(); idxCompareData++) {

                listCompareNum = (ArrayList<Integer>) listData.get(idxCompareData);

                if (listCompareNum.isEmpty())

                     continue;

                for (int idxMinNum = 0; idxMinNum < listMinNum.size(); idxMinNum++) {

                     tmp = (int) listMinNum.get(idxMinNum);

                     for (int idxCompareNum = 0; idxCompareNum < listCompareNum.size(); idxCompareNum++) {

                           if (tmp == (int) listCompareNum.get(idxCompareNum)) {

                                listCompareNum.remove(idxCompareNum);

                                break;

                           }

                     }

                     if (listCompareNum.isEmpty())

                           break;

                }

           }

     }

     

     /* 남은 숫자들을 모두 곱한다. */

     int result = 1;

     for (int i = 0; i < listData.size(); i++) {

           listCompareNum = (ArrayList<Integer>) listData.get(i);

           if (listCompareNum.isEmpty())

                continue;

           for(int j=0; j<listCompareNum.size(); j++) {

                result *= (int)listCompareNum.get(j);

                System.out.println("" + (int)listCompareNum.get(j));

           }

     }

     

     System.out.println("" + result);

}

결과는 아래와 같으며 문제의 정답이다.

2

3

2

5

7

2

3

11

13

2

17

19

232792560

total time(ms): 2.675267

마치며

컴퓨터의 가장 큰 장점은 반복작업 수행 능력이 뛰어나다는 것이다. 수천번 수만번의 계산도 빠르고 정확하게 수행한다.

때문에 아래와 같은 방법으로도 정답을 도출할 수 있다.

int i, j, result = 0;

boolean selector = true;

for (i = 1;; i++) {

     for (j = 1; j < 21; j++) {

           if ((i % j) != 0) {

                selector = false;

                break;

           }

     }

     if (selector) {

           result = i;

           break;

     }

     selector = true;

}

System.out.println("" + result);

단순히 숫자를 1씩 증가시키며 해당 숫자가 1부터 20까지의 모든 숫자와 나누어 떨어지면 해당 숫자를 출력하는 알고리즘이다.

결과는 아래와 같으며 정답을 도출해냈다.

232792560

total time(ms): 3641.699495

이러한 구현은 매우 간단하지만 연산 시간을 비교해봤을 때, 본문의 풀이 방법보다 무려 1800배나 시간이 오래 걸린다. (본문의 알고리즘의 경우 연산 시간이 약 2ms 이다.)

필자는 같은 작업을 해도 수행 시간을 단축시키고 코드를 최적화 하는 능력을 기르는 것이 문제를 푸는 목적이라고 생각한다.

때문에 다소 복잡할 수 있지만 효율적인 방법의 풀이법을 소개했다.

github