Project Euler 4: 세 자리 수 두 개의 곱에서 가장 큰 회문수를 위에서부터 찾기

Project Euler 시리즈의 네 번째 문제입니다. 모든 경우를 다 시험해도 금방 끝나는 크기라서, 이번 글의 관심사는 “더 빠른 공식”보다 탐색을 어디서 멈춰도 되는가입니다. 큰 곱부터 차례로 보면서 더 볼 필요가 없는 부분을 잘라 내는데, 잘라 낸 곳에 답이 숨어 있지 않다는 것을 제대로 증명해 둡니다. 이 논리는 뒤의 문제에서도 계속 쓰입니다.

스포일러 주의: 이 글에는 풀이 전체와 정답이 들어 있습니다. 직접 먼저 풀어 보고 싶다면 원래 문제부터 보세요. 이 시리즈의 글에는 광고를 싣지 않습니다. 문제 본문의 라이선스(CC BY-NC-SA 4.0)가 비영리 조건을 두기 때문입니다.

문제

앞에서 읽어도 뒤에서 읽어도 같은 수를 회문수(palindrome)라고 합니다. 문제에 나온 예로, 두 자리 수 두 개의 곱으로 만들 수 있는 가장 큰 회문수는 9009 = 91 × 99입니다. 같은 방식으로 세 자리 수 두 개의 곱으로 만들 수 있는 가장 큰 회문수를 구하는 것이 문제입니다.

두 인수는 각각 100부터 999까지의 정수이고, 구할 것은 그 곱 중 회문수인 것의 최댓값 하나입니다.

필요한 배경 지식

회문수 판정. 수 n의 십진 자릿수를 거꾸로 붙여 만든 수를 rev(n)이라고 하면, n이 회문수인 것은 rev(n) = n과 같습니다. rev(n)은 문자열로 바꾸지 않고 정수 연산만으로 만들 수 있습니다. n % 10으로 마지막 자리를 꺼내 결과의 뒤에 붙이고(결과 × 10 + 자리), n을 10으로 나눈 몫으로 바꾸기를 n이 0이 될 때까지 반복합니다. 예를 들어 9009는 9 → 90 → 900 → 9009가 되어 회문수이고, 9019는 9 → 91 → 910 → 9109가 되어 아닙니다. 끝자리가 0인 수(예: 10)는 거꾸로 하면 앞자리 0이 사라져 원래 수와 달라지므로 회문수가 아닙니다. 맨 앞자리가 0인 수는 없으니 이것이 맞는 판정입니다.

곱의 단조성. 양의 정수 a를 고정하면 a × b는 b에 대해 증가합니다. b를 위에서부터 1씩 줄이면 곱은 a씩 줄어듭니다. 그래서 b를 내려가며 보다가 어떤 곱이 기준값 이하가 되면, 그 뒤의 곱도 모두 기준값 이하입니다. 같은 이유로 b의 상한이 hi일 때 a × b의 최댓값은 a × hi이고, a가 작아질수록 이 값도 작아집니다.

짝수 자리 회문수는 11의 배수입니다. 네 자리 회문수 abba를 자리별로 풀면

abba   = 1000a + 100b + 10b + a          = 1001a + 110b          = 11 × (91a + 10b)
abccba = 100001a + 10010b + 1100c                                = 11 × (9091a + 910b + 100c)

입니다(1001 = 11 × 91, 100001 = 11 × 9091, 10010 = 11 × 910, 1100 = 11 × 100). 11은 소수이므로, 짝수 자리 회문수가 x × y로 쓰이면 x와 y 중 적어도 하나는 11의 배수입니다. 최종 알고리즘은 이 사실을 쓰지 않지만, 작은 예를 손으로 검산할 때와 “더 생각해 볼 것”에서 씁니다.

가장 단순한 방법

100부터 999까지의 a와 b를 모두 짝지어 곱을 만들고, 회문수인 것 중 가장 큰 것을 고르면 됩니다.

best = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        if str(a * b) == str(a * b)[::-1]:
            best = max(best, a * b)

세 자리 수는 900개이므로 곱은 900 × 900 = 810000개이고, 각각 자릿수만큼의 회문 판정을 합니다. 이 정도는 요즘 컴퓨터에서 금방 끝나므로 틀린 방법은 아닙니다. 다만 자릿수를 d로 일반화하면 곱의 개수가 (9 × 10^(d−1))², 즉 d가 하나 늘 때마다 100배가 됩니다. 또 이 방법은 답이 나온 뒤에도 남은 곱을 끝까지 봅니다. 가장 큰 회문수를 찾는 문제인데, 큰 곱이 어디 있는지 이미 아는 정보를 쓰지 않는 것입니다.

풀이 유도

인수의 범위를 lo = 10^(d−1), hi = 10^d − 1로 둡니다(세 자리면 100과 999). 가장 단순한 방법에서 버려도 되는 일을 하나씩 찾습니다.

1단계: 순서를 바꾼 짝은 한 번만 봅니다. a × b = b × a이므로 a ≤ b인 짝만 보면 됩니다. 곱의 개수가 거의 절반이 됩니다.

2단계: 큰 곱부터 봅니다. a를 hi부터 lo까지 내려가며, 각 a마다 b를 hi부터 a까지 내려갑니다. 배경 지식의 단조성에 따라 한 a 안(이하 “a 행”)에서는 곱이 계속 줄어듭니다. 그래서 a 행에서 처음 만난 회문수가 그 행에서 가장 큰 회문수이고, 그 행의 나머지는 볼 필요가 없습니다.

3단계: 지금까지의 최댓값과 비교합니다. 지금까지 찾은 가장 큰 회문수를 best라고 합니다. a 행을 내려가다 곱이 best 이하가 되면 그 행의 남은 곱은 모두 best 이하이므로 행을 멈춥니다.

4단계: 바깥 반복도 멈춥니다. a 행의 가장 큰 곱은 a × hi입니다. a × hi ≤ best이면 a 행에는 best를 넘는 곱이 없고, a보다 작은 행은 a × hi보다 더 작으므로 역시 없습니다. 여기서 탐색 전체를 끝냅니다.

작은 예로 손 검산. 두 자리(lo = 10, hi = 99)로 따라가 봅니다. 99 행은 99 × 99 = 9801 하나뿐이고 회문수가 아닙니다. 98 행부터 92 행까지는 각 행의 곱이 회문수가 되려면 배경 지식에 따라 두 인수 중 하나가 11의 배수여야 하는데, 92부터 99 사이의 11의 배수는 99뿐입니다. 그래서 확인할 곱은 b = 99인 경우뿐입니다.

92 × 99 = 9108    93 × 99 = 9207    94 × 99 = 9306    95 × 99 = 9405
96 × 99 = 9504    97 × 99 = 9603    98 × 99 = 9702    99 × 99 = 9801

어느 것도 회문수가 아니므로 99 행부터 92 행까지 best는 0으로 남습니다(알고리즘은 이 행들을 끝까지 내려가며 봅니다). 91 행의 첫 곱 91 × 99 = 9009는 회문수이므로 best = 9009가 되고 행을 멈춥니다. 다음 90 행에서는 90 × 99 = 8910 ≤ 9009이므로 4단계에 따라 탐색이 끝납니다. 결과는 9009 = 91 × 99로 문제의 예와 같습니다.

최종 알고리즘

1. lo = 10^(d−1), hi = 10^d − 1, best = 0으로 시작합니다.
2. a = hi, hi − 1, …, lo 순서로:
   1. a × hi ≤ best이면 전체를 멈춥니다.
   2. b = hi, hi − 1, …, a 순서로 곱 p = a × b를 만들어, p ≤ best이면 이 행을 멈추고, p가 회문수이면 best = p로 두고 이 행을 멈춥니다.
3. best를 돌려줍니다. 회문수가 하나도 없으면 0이지만, 이 글에서 쓰는 d = 1, 2, 3에서는 그런 일이 없습니다.
4. 정답을 출력하기 전에 작은 입력을 확인합니다. 회문 판정은 9009 → 참, 9019 → 거짓, 7 → 참, 10 → 거짓이고, 한 자리 결과는 9, 두 자리 결과는 9009여야 합니다. 하나라도 다르면 0이 아닌 종료 코드로 끝냅니다.

정확성 증명

a 행을 처리하기 직전마다 다음이 성립합니다(불변식).

best는 a < x ≤ y ≤ hi인 모든 짝 (x, y)의 곱 중 회문수인 것의 최댓값이다(없으면 0).

처음(a = hi)에는 그런 짝이 없고 best = 0이므로 성립합니다. a 행을 처리할 때 행을 멈추는 경우는 둘입니다. 곱이 best 이하가 되어 멈추면, 단조성에 따라 건너뛴 곱은 모두 best 이하이므로 최댓값을 바꿀 수 없습니다. 회문수를 만나 멈추면, 그 곱이 행에서 가장 큰 회문수이고 건너뛴 곱은 그보다 작습니다. 행 안에서 best가 바뀌는 것은 best보다 큰 회문수를 만났을 때뿐입니다. 어느 쪽이든 행을 마치면 best는 x ≥ a인 짝까지의 최댓값이 되어, 다음 행(a − 1)에서 불변식이 성립합니다.

바깥 반복이 4단계로 멈출 때는 남은 모든 짝 (x, y)에 대해 x ≤ a, y ≤ hi이므로 x × y ≤ a × hi ≤ best입니다. 남은 곱은 best를 넘지 못합니다. 반복이 lo까지 다 돌아 끝나면 모든 짝을 본 것입니다. 두 경우 모두 best는 lo ≤ x ≤ y ≤ hi인 모든 짝의 최댓값이고, 1단계의 대칭성에 따라 순서를 따지지 않은 모든 짝의 최댓값과 같습니다.

복잡도

최악의 경우. N = hi − lo + 1 = 9 × 10^(d−1)이라고 하면 a ≤ b인 짝은 N(N + 1) / 2개이고, 회문 판정 한 번은 곱의 자릿수(2d 이하)에 비례합니다. 가지치기가 전혀 일어나지 않는다고 가정하면 시간은 O(N² · d)로, 가장 단순한 방법의 절반쯤입니다. 세 자리에서는 N = 900이라 최악이라도 405450개의 곱입니다. 저장하는 값은 몇 개뿐이라 추가 공간은 O(1) 입니다.

실제로는 훨씬 일찍 멈춥니다. 큰 회문수를 일찍 찾으면 3단계와 4단계로 대부분의 행이 몇 번의 곱만에 끝나거나 아예 열리지 않습니다. 몇 번 만에 끝나는지는 입력에 따라 다르고 미리 보장할 수 있는 식이 없으므로, 여기서는 최악의 상한만 복잡도로 적습니다. 실제 반복 횟수는 이 글에서 따로 재지 않았습니다.

정수 범위.

• 세 자리에서 가장 큰 곱은 999 × 999 = 998001이라 32비트 정수에도 들어갑니다. C++ 구현은 d를 1부터 9까지 쓸 수 있게 unsigned long long을 썼습니다. 그 범위에서 곱은 (10^9 − 1)² < 10^18이고, unsigned long long은 표준이 최소 64비트(최댓값 약 1.8 × 10^19 이상)를 보장하므로 넘치지 않습니다. 부호 없는 타입이라 넘치더라도 정의되지 않은 동작은 아니지만, 이 범위에서는 애초에 넘칠 일이 없습니다.
• 회문 판정에서 만드는 거꾸로 된 수는 매 단계 원래 수보다 자릿수가 많지 않으므로 원래 수와 같은 자릿수 이하, 즉 10^18 미만입니다. 4단계 조건의 a × hi도 같은 상한 안에 있습니다.
• 반복 변수도 부호 없는 타입이지만 a >= lo(lo ≥ 1), b >= a(a ≥ 1)에서 멈추므로, 0 아래로 내려가 큰 값으로 돌아가는 일이 없습니다.
• Python의 int는 정밀도에 제한이 없어 넘칠 일이 없습니다. 알고리즘은 C++와 같습니다.

C++17 구현

#include <iostream>

// True when the decimal digits of n read the same in both directions.
bool is_palindrome(unsigned long long n) {
    unsigned long long reversed = 0;
    for (unsigned long long rest = n; rest > 0; rest /= 10) {
        reversed = reversed * 10 + rest % 10;
    }
    return reversed == n;
}

// Largest palindrome that is a product of two numbers with exactly `digits` digits.
// Only pairs a <= b are tried. For a fixed a, b goes down from the top, so the
// products go down too: stop at the first palindrome or once a product is no
// larger than the best so far. Stop the outer loop once even a * hi cannot beat it.
// Meant for 1 <= digits <= 9, where every value fits in 64 bits.
unsigned long long largest_palindrome_product(int digits) {
    unsigned long long lo = 1;
    for (int i = 1; i < digits; ++i) {
        lo *= 10;
    }
    const unsigned long long hi = lo * 10 - 1;
    unsigned long long best = 0;
    for (unsigned long long a = hi; a >= lo; --a) {
        if (a * hi <= best) {
            break;
        }
        for (unsigned long long b = hi; b >= a; --b) {
            const unsigned long long product = a * b;
            if (product <= best) {
                break;
            }
            if (is_palindrome(product)) {
                best = product;
                break;
            }
        }
    }
    return best;
}

int main() {
    if (!is_palindrome(9009) || is_palindrome(9019) || !is_palindrome(7) ||
        is_palindrome(10) || largest_palindrome_product(1) != 9 ||
        largest_palindrome_product(2) != 9009) {
        return 1;
    }
    std::cout << largest_palindrome_product(3) << '\n';
    return 0;
}

작은 예의 확인은 assert가 아니라 if로 했습니다. assert는 NDEBUG가 정의된 빌드에서 사라지기 때문입니다. 확인이 하나라도 틀리면 return 1로 0이 아닌 종료 코드를 냅니다.

Python 3 구현

def is_palindrome(n: int) -> bool:
    """True when the decimal digits of n read the same in both directions."""
    reversed_n = 0
    rest = n
    while rest > 0:
        reversed_n = reversed_n * 10 + rest % 10
        rest //= 10
    return reversed_n == n


def largest_palindrome_product(digits: int) -> int:
    """Largest palindrome that is a product of two numbers with exactly `digits` digits.

    Only pairs a <= b are tried. For a fixed a, b goes down from the top, so the
    products go down too: stop at the first palindrome or once a product is no
    larger than the best so far. Stop the outer loop once even a * hi cannot beat it.
    """
    lo = 10 ** (digits - 1)
    hi = lo * 10 - 1
    best = 0
    for a in range(hi, lo - 1, -1):
        if a * hi <= best:
            break
        for b in range(hi, a - 1, -1):
            product = a * b
            if product <= best:
                break
            if is_palindrome(product):
                best = product
                break
    return best


def main() -> None:
    if (
        not is_palindrome(9009)
        or is_palindrome(9019)
        or not is_palindrome(7)
        or is_palindrome(10)
        or largest_palindrome_product(1) != 9
        or largest_palindrome_product(2) != 9009
    ):
        raise SystemExit(1)
    print(largest_palindrome_product(3))


if __name__ == "__main__":
    main()

C++와 같은 알고리즘, 같은 작은 예입니다. 회문 판정도 C++와 맞추려고 str(n)[::-1] 대신 정수 연산으로 했고, 자릿수를 떼어 낼 때는 정수 나눗셈 //=를 씁니다. range(hi, lo - 1, -1)처럼 끝값이 포함되지 않는 점 때문에 끝을 하나 더 낮춰 두었습니다. 작은 예가 틀리면 raise SystemExit(1)로 종료 코드 1을 냅니다. assert는 python -O로 실행하면 제거되므로 쓰지 않았습니다.

정답과 검증

세 자리 수 두 개의 곱으로 만들 수 있는 가장 큰 회문수는 906609 = 913 × 993입니다. 아래에서는 이 값을 그냥 “결과”라고 부르겠습니다.

손으로 확인할 수 있는 부분은 다음과 같습니다.

• 곱. 913 × 993 = 913 × 1000 − 913 × 7 = 913000 − 6391이고, 이 값이 정확히 결과와 같습니다. 913과 993은 모두 세 자리 수입니다.
• 회문수. 결과는 여섯 자리이고, 앞 세 자리를 거꾸로 읽으면 뒤 세 자리가 됩니다.
• 11과의 관계. 결과는 11 × 82419이고, 913 = 11 × 83이라 인수 중 하나가 11의 배수라는 배경 지식의 사실과 맞습니다. 더 쪼개면 결과는 3 × 11 × 83 × 331이고, 993 = 3 × 331입니다.

이 결과가 “가장 큰” 것이라는 부분은 손 계산이 아니라 위의 정확성 증명과 프로그램 실행으로 보장합니다. 검증은 세 겹입니다.

1. 작은 예. 두 프로그램 모두 답을 출력하기 전에 회문 판정 네 가지(9009, 9019, 7, 10)와 한 자리 결과 9, 두 자리 결과 9009를 확인하고, 다르면 0이 아닌 종료 코드로 끝납니다. 두 자리 결과 9009는 “풀이 유도”에서 손으로도 따라가 보았습니다.
2. 두 구현의 일치. 이 시리즈의 저장소에서는 검사 스크립트가 C++ 코드를 g++ -std=c++17 -O2 -Wall -Wextra -Werror로 컴파일해 실행하고(경고도 실패로 처리), Python 코드를 python3 -I -B로 실행합니다. 두 출력이 저장해 둔 answer.txt와 바이트 단위로 같아야 하고, 0이 아닌 종료 코드나 시간 초과(C++ 1초, Python 10초)는 실패입니다. 시리즈 규칙상 이 검사를 통과한 코드만 글에 싣습니다.
3. 증명. 가지치기로 건너뛴 곱이 best를 넘을 수 없다는 것은 “정확성 증명”에서 보였습니다. 의심스럽다면 “가장 단순한 방법”의 코드를 그대로 실행해 결과를 비교해 볼 수 있습니다.

경계 사례

• 한 자리(d = 1): 1부터 9까지의 곱 중 한 자리 수는 모두 회문수이고, 두 자리 회문수 11, 22, …, 99는 모두 11의 배수라 한 자리 수 두 개의 곱이 될 수 없습니다. 그래서 답은 9(= 9 × 1 = 3 × 3)입니다. 알고리즘은 9 행부터 4 행까지 회문수를 못 찾고, 3 행의 마지막 곱 3 × 3에서 9를 찾습니다. 2 행은 2 × 9 = 18이 9보다 커서 열리지만 곱이 9 이하로 내려가면 멈추고, 1 행은 1 × 9 = 9 ≤ 9라서 4단계에 따라 탐색이 끝납니다.
• 끝자리가 0인 곱: 10, 9010처럼 0으로 끝나는 수는 회문수가 아닙니다. 정수로 거꾸로 하면 앞자리 0이 사라지므로 판정이 자연스럽게 거짓이 됩니다. 작은 예에 10 → 거짓이 들어 있습니다.
• 한 자리 수 판정: 7 같은 한 자리 수는 그 자체로 회문수입니다. 반복이 한 번 돌고 7 = 7이 됩니다.
• 행 안의 곱이 best와 같을 때: 3단계 조건은 <=입니다. 같은 값은 best를 바꾸지 않으므로 건너뛰어도 됩니다.

더 생각해 볼 것

• 11의 배수만 시험하기. 세 자리 수 두 개의 곱은 10000 이상이라 회문수라면 다섯 자리 또는 여섯 자리이고, 답이 여섯 자리 회문수라는 것을 알면 a나 b 중 하나가 11의 배수여야 합니다. a가 11의 배수가 아니면 b를 11의 배수로만 내려가게 바꿔 보세요. 정확성 증명의 어느 부분을 고쳐야 할까요? 다섯 자리 회문수는 11의 배수라는 보장이 없다는 점도 함께 따져 봐야 합니다.
• 회문수부터 만들기. 반대로 999999, 998899, 997799, …처럼 여섯 자리 회문수를 큰 것부터 만들고, 100 이상 999 이하의 약수 x가 있으면서 몫도 세 자리인지 확인하는 방법도 있습니다. 앞 세 자리만 정하면 회문수가 정해진다는 점을 쓰면 됩니다. 어느 쪽이 시험하는 수가 적을지 생각해 보세요.
• 자릿수 늘리기. d = 4, 5, …로 늘리면 가지치기의 효과가 어떻게 변할까요? 위 C++ 코드는 d ≤ 9에서 64비트 안에 들어가지만, 그때도 최악의 상한은 O(N² · d)입니다.
• 다른 진법. is_palindrome은 십진수 자릿수만 봅니다. 진법을 인자로 받도록 바꾸려면 어떻게 해야 할까요? 0으로 끝나는 수는 회문수가 아니라는 논리도 그대로 성립할까요?

출처와 라이선스

• Project Euler, Problem 4 — 원래 문제. 이 글의 “문제” 절은 그 내용을 직접 요약한 것이고, 원문과 같은 CC BY-NC-SA 4.0으로 공유합니다. 문제의 저작자 표시는 Project Euler입니다.
• Project Euler, Copyright — 문제 본문의 라이선스와 링크 방식. 비영리 조건에 따라 이 글에는 광고를 싣지 않습니다(ads: false).
• 풀이, 증명, 코드는 직접 쓴 것입니다. Project Euler의 해설(overview), 포럼, 회원 전용 자료나 다른 풀이 사이트는 참고하지 않았습니다. Motitory는 Project Euler와 제휴나 후원 관계가 없고, Project Euler가 이 글을 검토하지도 않았습니다.