Problem 004 : Largest palindrome product (5%)

Description

original

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.

간략해석

세자리수 * 세자리수를 한 결과값 중 팰린드롬이 되는 최댓값을 구하시오.

Idea & Algorithm

naive idea

3자리수는 100부터 999까지이므로 900개밖에 안된다. 또한 수를 팰린드롬 체크하는 것은 자릿수 정도로 체크가 되고 최대 6자리니 전체적인 연산량은 4,860,000회 정도밖에 되지 않는다.

그러므로 그냥 나이브하게 풀면된다.

advanced idea

source code

이 당시에는 팰린드롬 체크를 조건문으로 구현했다. 현재는 각자리수를 vector에 담아서 팰린드롬을 체크하는 방식을 사용하고 있다.

#include <stdio.h>

int check_palin(int n){
    if(n<100000){
        if(n/10000==n%10&&(n/1000)%10==(n/10)%10)
            return n;
    }
    else{
        if(n/100000==n%10&&(n/10000)%10==(n/10)%10&&(n/1000)%10==(n/100)%10)
            return n;
    }
    return 0;
}

int maxnum;

int main(){    
    for(int i = 100 ; i < 1000 ; i++){
        for(int j = 100 ; j < 1000 ; j++){
            int tmp = check_palin(i*j);
            maxnum = maxnum > tmp ? maxnum : tmp;
        }
    }
    printf("%d",maxnum);
}

Problem 004