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

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

 

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

 

#include <stdio.h>
int main() {
int i, j;
int x;
int sol = 0;
int n1, n2, n3, n4, n5, n6;
for (i = 999; i > 100; i - )
	for (j = 999; j > 100; j - ){
		x = i * j;
		n1 = x / 100000;
		x = x % 100000;
		n2 = x / 10000;
		x = x % 10000;
		n3 = x / 1000;
		x = x % 1000;
		n4 = x / 100;
		x = x % 100;
		n5 = x / 10;
		x = x % 10;
		n6 = x / 1;
		if ((n1 == n6) && (n2 == n5) && (n3 == n4)){
			printf("n1 = %d,n2 = %d,n3 = %d,n4 = %d,n5 = %d,n6 = %d \n", n1, n2, n3, n4, n5, n6);
			x = i*j;
			if (x > sol){
				sol = x;
				break;
			}
		}
	}
printf("%d \n", sol);
}

3자리 x 3자리로 이루어진 가장 큰 대칭수는 6자리라고 단정 짓고 짠 알고리즘,

 

 

해답:

대칭수 P는 x,y,z로 구성 가능. P= a x b(a와 b는 100보다 크고 999보다 작은 정수)

P는 반드시 적어도 6자리로 긴 정수 일것이다. 왜냐하면 111111=143 x 777 이기 때문(P는 3자리 x 3자리로 이루어진 대칭수 111111보다 크거나 같을 것)

따라서,

 

P=100000x+10000y+1000z+100z+10y+x

P=100001x+10010y+1100z 

P=11(9091x+910y+100z)

 

11은 소수로 반드시 a, b는 11을 약수로 가짐

따라서 11로 나누어 지지 않는다면 대칭수가 아님.

 

largestPalindrome = 0

a = 999

while a >= 100

if a mod 11 = 0

b = 999

db = 1

else

b = 990 //The largest number less than or equal 999

 //and divisible by 11

db = 11

while b >= a

if a*b <= largestPalindrome

break

if isPalindrome(a*b)

largestPalindrome = a*b

b = b-db

a = a-1

output largestPalindrome

'Programing > Algorithm' 카테고리의 다른 글

프로젝트 오일러 6번  (0) 2015.02.10
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 3번  (0) 2015.02.10
프로젝트 오일러 2번  (0) 2015.02.10
Kadane's Algorithm  (0) 2015.02.10
Posted by kimmayer

블로그 이미지
IT 기술들 정리, 독후감을 주로 남깁니다!
kimmayer

공지사항

Yesterday
Today
Total

달력

 « |  » 2024.3
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함