2013. 11. 13.

Project Euler - 문제 4번

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

 문제 4번 : Palindromic 숫자는 앞뒤로 읽어도 같은 숫자를 말한다. 두 자리 숫자의 곱셈으로 이루어진 가장 큰 palindromic  숫자는  9009 = 91 × 99 이다. 그러면 세 자리 숫자의 곱셈으로 이루어진 가장 큰  숫자는 얼만인가?



 약간씩 문제가 어려워지기 시작했습니다. 앞뒤로 읽어도 같은 숫자이며, 세 자리 숫자의 곱셈으로 이루어진 가장 큰 숫자를 찾는 문제인데, 이를 위해서는 앞뒤로 읽어도 정말 같은 숫자인지 체크를 해 주어야 합니다. 그래서 저는 아래의 코드를 사용해서 숫자가 앞뒤로 읽어도 같은지 체크 한 뒤에 메인 코드를 진행하였습니다.

int checker(int n)
{
 int l = length(n);
 int num[l-1];
 int count = 0;
 
 for(int a = 0; a < l; a++)
 {
  num[a] = n%10;
  n = n/10;
 }
 for(int a = 0; a < l/2; a++)
 {
  if(num[a] == num[l-1-a])
   count++;
 }
 if(count == l/2)
  return 1;
 else
  return 0;
}

 여기서 숫자 n의 길이 length(n)은 함수로 정의하는데, 길이를 측정하는 방법은 여러 가지가 있을 수 있습니다. 그 후에 세 자리 숫자들의 곱을 일일히 checker에 넣어서 확인하고 그 결과를 바탕으로 가장 큰 값을 찾아 나가면 될 것 같습니다.

int main()
{
 clock_t start = clock();
 
 int result = 0; 
    for(int i = 100; i < 1000; i++)
    {
     for(int j = 100; j < i+1; j++)
     {
      if(checker(i*j) == 1 && i*j > result)
       result = i*j;
     }
    }
    
    clock_t end = clock();
    cout << "결과 : " << result << endl;
    cout << "시간 : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

 그러면 결과가 아래와 같이 나옵니다. 당연히 앞뒤로 봐도 같은 숫자가 나오겠지요.


 이번엔 바로 정답이 나왔습니다.


댓글 없음:

댓글 쓰기