프로젝트 오일러(Project Euler) 4번문제

Problem 4

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

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

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

풀이

  이제 문제가 조금씩 난이도가 증가하는 느낌이 든다. 프로그래밍 적으로 대칭수를 판별하는 것이 이번 문제의 핵심인 듯 하다. 방법에는 여러가지가 있을 수 있다. 그중에서 숫자를 나누기연산을 통해 12345를 54321로 뒤집어주는 방법과 12345를 문자열로 만드는 방법이 많이 사용된다. 나는 두번째 방법과 비슷하게 int형 배열을 만들어서 문제를 해결하였다. check_palindrome 이라는 함수를 만들어서 대칭수를 판별해 주고 main에서는 그냥 세자리수를 곱한 모든 경우의 수를 다 보내주기만 한다.

  

최대한 주석을 세세하게 달아 보았는데 오히려 보기 약간 불편한 것 같기도 하다...

#include <stdio.h>
#include <stdlib.h>
 
//100 x 100 = 10000, 999 x 999 = 998001
//4 ~ 6 자리만 체크하면됨
int check_palindrome(int num)  
{
    int length = 0, i = 5; // i는 arr의 최대 인덱스값
    char arr[6] = { 0, };
 
    while (num > 0)
    {
        arr[i] = num % 10;    // 현재 num의 일의 자리 숫자를 arr에 넣음
        num /= 10;    // num에서 일의 자리 숫자를 제거함
        length++;    // 길이를 1 증가
        i--;    // 인덱스값 1 감소
    }
 
    if (arr[5] == arr[6-length] && arr[4] == arr[7-length])
    {    // 대칭을 판단한다. 여기서 숫자가 4~5자리이면 대칭수로 판단. 1을 반환한다.
        if (length == 6 && arr[3] == arr[2])
        {    // 길이가 6이면서 대칭이기까지 하면 대칭수
            return 1;    
        }
    }
    return 0;    // 모든 과정에서 걸리지 않으면 대칭수가 아님. 0반환
}
 
void main()
{
    int answer = 0;    // 답이 저장 될 변수
 
    for (int i = 100; i < 1000; i++)
    {
        for (int j = i; j < 1000; j++)    // 100 X 101과 101 X 100은 같기 때문에 이와같이 조건을 줌
        {
            if (check_palindrome(i*j) && i*j > answer)
            {    // 함수가 1을 반환하고 i*j가 현재 answer보다 크면
                answer = i*j;    // answer 갱신
            }
        }
    }
    printf("%d\n", answer);
}
 

결과