Project Euler

Project Euler 문제풀이를 통해 문제해결 능력과 프로그래밍 기법 향상

Project Euler Project Euler 문제풀이를 통해 문제해결 능력과 프로그래밍 기법 향상
본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

#4. Largest palindrome product

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

 


Keyword : 대칭수

대칭수의 특징 abccba ==> a*100000 + b*10000 + c*1000 + c*100 + b*10 + a

             두 자리 수 곱셉의 대칭수 ( 100 ~ 9801 )
             1000 이상이라고 가정하면 대칭수는 ?
              = 1000*a + 100*b + 10*b + a
              = 1001*a + 110*b
              = 7*11*13*a + 2*5*11*b
              = 11*(7*13*a + 2*5*b)
            < a = 9, b = 0 > ==> (7*13) * (11*9) = 91 * 99 = 9009

             세 자리 수 곱셉의 대칭수 ( 10000 ~ 998001 )
             100000 이상이라고 가정하면 대칭수는 ?
              = 100000*a + 10000*b + 1000*c + 100*c + 10*b + a
              = 100001*a + 10010*b + 1100*c
              = 11*9091*a + 11*910*b + 11*100*c

              = 11*(9091*a + 910*b + 100*c)

C / C++

 

        int number;    // number 100000 이상이라 가정하고 998001(=999*999) 이하이다.

        int a = 1;     // a = 1 ~ 9

        int b = 0;     // b = 0 ~ 9

        int c = 0;     // c = 0 ~ 9

 

        // 대칭수의 소인수는 11을 무조건 포함한다. 따라서 둘중 한 수는 세 자리 수 이며 11의 배수

        // 따라서 multiplier = 10 ~ 90 --> 11 * multiplier = 110 ~ 990

        int multiplier;

        int m;

 

        // 결과저장 변수들

        int first;

        int second;

        int result;

 

        while ( a<10 ) // c=0~9, b=0~9, a=1~9 까지의 루프

        {

               number = 11*(9091*a + 910*b + 100*c); // 해당 대칭수

               multiplier = 9;       // 11을 포함하는 대칭수의 약수를 구하기 위한 곱셈 값

               while ( multiplier++ < 90 )  

               {

                       m = 11*multiplier;

                       if ( !(number % m) )   // 11을 포함하는 대칭수의 약수를 찾음

                       {

                              if ( number / m > 999 ) break; // 나머지 다른 수가 999 이하인가?

                              first = m;

                              second = number / m;

                       }

               } 

               // c~b~a 차례대로 증가를 위함.

               if ( !(++c %= 10) )

                       if ( !(++b %= 10) )

                              a++;

        }

 

        result = first * second;

        cout << "Question 4 : " << first << " * " << second << " = " << result << endl;

  • 봤어요 (0명)

댓글

댓글 본문
작성자
비밀번호
버전 관리
학생
현재 버전
선택 버전
graphittie 자세히 보기