본문 바로가기

문제풀기/프로젝트 오일러

프로젝트 오일러 문제 - 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.

 

대칭수(?)를 찾는 문제이다.

 

 

 

Sol.)

 

아주 단순하게 세자리수 곱하기 세자리수는 아무리 커봤자 6자리를 넘지 못한다. (999*999=998001)

그리고 대칭수가 되기 위해서는 자리수가 짝수여야 한다.(2자리수, 4자리수, 6자리수)

대칭수 중 가장 큰 수를 찾는 것이기 때문에, 아마 그 수는 6자리일 것이라는 가정을 하고, 곱하는 두 수를 가장 큰 수(999)부터 설정하여 점점 작은수로 만들어보는 것이 반대의 경우보다 훨씬 빠를 것이다.

그리고 두 수의 곱이 5자리 미만으로 내려가면 즉시 실행을 종료시킨다.(실행속도개선 및 예외발생가능성 없애기)

그리고 곱한 수를 자리수대로 비교하려면 아마도 String 이나 char형처럼 문자화 시켜서 비교를 해야 가능한 것으로 보인다.

아래는 그렇게 만든 코드다.

 

import java.math.*;
import java.util.*;

class ProjectEuler{
 public static void main(String[] args){
  int a=1, b=1;
  Integer result = new Integer(a*b);
  String str="";

STOP: for(a=1000; a>100; a--){
   for(b=1000; b>100; b--){
    str = result.toString(a*b);
    if(a*b<99999){
     break STOP;
    }
    if(str.charAt(0)==str.charAt(5) && str.charAt(1) == str.charAt(4) && str.charAt(2) == str.charAt(3)){
     System.out.println(str);
    }
   }
  }  
 }
}

 

답은 906609 로 간단히 나왔다.