Project Euler 8: 1000자리 수에서 인접한 13자리의 최대 곱을 0을 세는 슬라이딩 윈도로 구하기

Project Euler 시리즈의 여덟 번째 문제입니다. 창마다 숫자 13개를 곱해 보는 방법만으로도 답은 금방 나옵니다. 이 글에서는 한 걸음 더 나아가, 창을 한 칸 밀 때 나가는 숫자로 나누고 들어오는 숫자를 곱하는 슬라이딩 윈도를 만듭니다. 이때 부딪히는 문제가 0입니다. 0을 곱하는 대신 개수만 세면 0으로 나누는 일이 생기지 않는다는 것을 보이고, 곱이 32비트에 들어가지 않는 이유도 따져 봅니다.

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

문제

원래 문제에는 1000자리 수 하나가 주어집니다. 그 수에서 연속으로 붙어 있는 숫자 4개의 곱 중 가장 큰 것은 9 × 9 × 8 × 9 = 5832라고 예로 보여 줍니다. 같은 수에서 연속으로 붙어 있는 숫자 13개의 곱 중 가장 큰 값을 구하는 것이 문제입니다.

따로 받는 입력은 없습니다. 수는 원래 문제 페이지에 있고, 이 글의 코드에 그대로 옮겨 넣었습니다. 이 글에서는 자릿수를 n(= 1000), 창의 길이를 k(= 13)로 쓰고, 왼쪽에서 i번째 숫자(0부터 셈)를 dᵢ로 씁니다. 길이 k인 창은 n − k + 1 = 988개입니다. 구할 것은 정수 하나입니다.

필요한 배경 지식

슬라이딩 윈도. 길이 k인 창을 왼쪽 끝에서 오른쪽 끝까지 한 칸씩 밀면, 한 번 밀 때마다 바뀌는 것은 왼쪽에서 나가는 숫자 하나와 오른쪽에서 들어오는 숫자 하나뿐입니다. 창에 대해 들고 다니는 값을 이 두 숫자만으로 고칠 수 있다면, 창마다 처음부터 다시 계산할 필요가 없습니다.

곱에 0이 있으면 곱은 0입니다. 창에 0이 하나라도 있으면 그 창의 곱은 0입니다. 그리고 0으로는 나눌 수 없습니다. 그래서 “나가는 숫자로 나눈다”는 생각은 나가는 숫자가 0일 때 그대로는 통하지 않습니다(풀이 유도 2단계).

정확한 나눗셈. 정수 a가 a = d × b(d ≠ 0)로 쓰이면 a / d는 나머지 없이 정확히 b입니다. 정수 나눗셈(C++의 /, Python의 //)이 버림을 해도 이 경우에는 버릴 것이 없습니다. 풀이에서 나눗셈은 늘 이 꼴로만 씁니다.

문자를 숫자로. 수는 문자열로 저장합니다. 문자 '0'부터 '9'까지는 문자 코드가 차례로 1씩 커지므로, 숫자 문자 c의 값은 c − '0'입니다. 프로그램은 답을 내기 전에 문자열이 정말 1000개의 '0'–'9'로만 되어 있는지 확인합니다.

고정 폭 정수. 부호 없는 32비트 정수가 담을 수 있는 가장 큰 값은 2³² − 1 = 4294967295, 64비트는 2⁶⁴ − 1 = 18446744073709551615입니다. 넘치면 값이 조용히 돌아가 틀린 답이 나옵니다. 숫자 13개의 곱이 어느 쪽에 들어가는지는 “복잡도”에서 따집니다.

가장 단순한 방법

창의 시작 위치마다 숫자 k개를 처음부터 곱하고, 그중 가장 큰 값을 고릅니다.

best = 0
for start in range(n - k + 1):
    product = 1
    for j in range(start, start + k):
        product *= d[j]
    best = max(best, product)

맞는 방법이고, 곱셈은 (n − k + 1) × k = 988 × 13 = 12844번이라 이 문제에서는 충분히 빠릅니다. 비용은 O(nk) 이고, 창이 길어질수록 한 창에 드는 일이 k에 비례해 늘어납니다. 그런데 이웃한 두 창은 숫자 k − 1개를 공유하므로, 같은 곱셈을 거의 k번씩 되풀이하고 있는 셈입니다. 아래에서는 창마다 드는 일을 상수로 줄입니다. 이 단순한 방법은 버리지 않고 구현 안에서 검산용으로 씁니다.

풀이 유도

1단계: 문제의 예를 손으로 확인합니다. 원래 문제가 강조해 둔 연속된 네 숫자 9, 9, 8, 9의 곱은 9 × 9 = 81, 81 × 8 = 648, 648 × 9 = 5832로 문제의 예와 같습니다. 이 네 자리가 정말 가장 큰 창인지는 손으로 다 볼 수 없으므로, 프로그램이 k = 4로 계산해 5832가 나오는지 확인합니다.

알고리즘을 손으로 따라가기 위한 작은 예도 하나 정합니다. 숫자열 3021945, k = 3이면 창은 다섯 개입니다.

3 0 2 → 0
0 2 1 → 0
2 1 9 → 18
1 9 4 → 36
9 4 5 → 180
최댓값: 180

2단계: 나누고 곱해서 창을 미는 생각과 그 함정. 창의 곱 P를 알고 있으면, 한 칸 밀 때 나가는 숫자 dₒᵤₜ와 들어오는 숫자 dᵢₙ으로 새 곱을 P / dₒᵤₜ × dᵢₙ으로 얻을 수 있을 것 같습니다. 0이 없으면 맞습니다. 그러나 위의 예에서 첫 창 3 0 2의 곱은 0이고, 0이 창에서 나가는 순간 “0 / 0”이 필요해집니다. 곱이 한 번 0이 되면 그 안에 무엇이 곱해져 있었는지 정보가 사라지기 때문입니다.

3단계: 0은 곱하지 않고 셉니다. 창에 대해 두 값을 들고 다닙니다.

• Z: 창 안의 0의 개수
• P: 창 안의 0이 아닌 숫자들의 곱(그런 숫자가 없으면 1)

그러면 창의 곱은 Z > 0이면 0, Z = 0이면 P입니다. 한 칸 밀 때는

• 나가는 숫자가 0이면 Z를 1 줄이고, 아니면 P를 그 숫자로 나눕니다.
• 들어오는 숫자가 0이면 Z를 1 늘리고, 아니면 P에 그 숫자를 곱합니다.

왜 0으로 나누지 않고, 나눗셈이 정확한가. 나눗셈은 나가는 숫자 d가 0이 아닐 때만 합니다. 그리고 P는 d를 포함한 창 안의 0이 아닌 숫자들의 곱이므로 P = d × (나머지 0이 아닌 숫자들의 곱)이고, P / d는 나머지 없이 정확히 그 나머지의 곱입니다. 0은 한 번도 P에 곱해지지 않으므로 P는 늘 1 이상이고, 창에 0이 남아 있는 동안에도 P는 0이 아닌 숫자들의 곱이라는 뜻을 그대로 유지합니다. “0이 남아 있는데 나눈다”는 상황 자체가 생기지 않습니다. 0은 Z로만 드나듭니다.

4단계: 빼고 나서 더합니다. 한 칸 밀 때 나가는 숫자를 먼저 빼고 들어오는 숫자를 나중에 넣습니다. 그러면 P에 곱해져 있는 숫자는 어느 순간에도 k개 이하라서 P ≤ 9ᵏ입니다. 순서를 바꾸면 잠깐 k + 1개가 곱해져 상한이 9ᵏ⁺¹로 커집니다(“복잡도”의 정수 범위).

3021945, k = 3에서 따라가 봅니다. i는 들어오는 숫자의 위치이고, i ≥ 3부터는 먼저 dᵢ₋₃을 뺍니다.

i=0: 3 들어옴          Z=0, P=3   (창이 아직 덜 참)
i=1: 0 들어옴          Z=1, P=3
i=2: 2 들어옴          Z=1, P=6   창 302 → Z>0이라 0, best=0
i=3: 3 나감, 1 들어옴  Z=1, P=2   창 021 → 0
i=4: 0 나감, 9 들어옴  Z=0, P=18  창 219 → 18, best=18
i=5: 2 나감, 4 들어옴  Z=0, P=36  창 194 → 36, best=36
i=6: 1 나감, 5 들어옴  Z=0, P=180 창 945 → 180, best=180

1단계에서 창마다 직접 곱한 결과와 같습니다. i = 3에서 P = 6을 3으로 나눈 6 / 3 = 2가 정확하고, i = 4에서 0이 나갈 때는 나누지 않고 Z만 줄였습니다.

최종 알고리즘

1. Z = 0, P = 1, best = 0으로 시작합니다.
2. i = 0부터 n − 1까지:
   • i ≥ k이면 dᵢ₋ₖ를 뺍니다(0이면 Z − 1, 아니면 P / dᵢ₋ₖ).
   • dᵢ를 넣습니다(0이면 Z + 1, 아니면 P × dᵢ).
   • i + 1 ≥ k(창이 꽉 참)이고 Z = 0이고 P > best이면 best = P로 둡니다.
3. best를 돌려줍니다. 창의 곱이 0인 경우는 best의 시작값 0과 같으므로 따로 비교하지 않아도 됩니다.

전제는 1 ≤ k ≤ n입니다(“경계 사례”).

정확성 증명

i번째 숫자를 처리한 직후의 창을 W(i) = { dⱼ : max(0, i − k + 1) ≤ j ≤ i }라 합시다. 다음 불변식이 성립합니다. “Z는 W(i) 안의 0의 개수이고, P는 W(i) 안의 0이 아닌 숫자들의 곱이다.”

• 시작. 처리 전의 창은 비어 있고 Z = 0, P = 1(빈 곱)입니다.
• i < k일 때. 숫자를 넣기만 하고 W(i) = W(i − 1) ∪ {dᵢ}이므로, 넣는 규칙대로 Z나 P를 고치면 불변식이 유지됩니다.
• i ≥ k일 때. W(i)는 W(i − 1)에서 dᵢ₋ₖ를 빼고 dᵢ를 넣은 것입니다. dᵢ₋ₖ가 0이면 Z − 1이 맞고, 0이 아니면 3단계의 이유로 P / dᵢ₋ₖ가 정확히 나머지 0이 아닌 숫자들의 곱입니다. 그다음 dᵢ를 넣는 것은 앞의 경우와 같습니다.
• 따라서 i + 1 ≥ k인 각 i에서 W(i)는 정확히 dᵢ₋ₖ₊₁ … dᵢ의 k개이고, 그 곱은 Z > 0이면 0, 아니면 P입니다. 이런 i는 k − 1부터 n − 1까지 n − k + 1개로, 모든 창을 한 번씩 봅니다. best는 그 곱들 중 최댓값(모두 0이면 0)입니다.

복잡도

• 시간. 숫자 하나마다 비교 몇 번과 많아야 나눗셈 한 번, 곱셈 한 번이므로 O(n) 입니다. 창의 길이 k와 상관이 없습니다. 가장 단순한 방법의 O(nk)에 비해 k배가 줄었습니다.
• 공간. 숫자열 자체를 빼면 Z, P, best 같은 값 몇 개뿐이라 O(1) 입니다.

정수 범위.

• P와 best는 0이 아닌 숫자 k개 이하의 곱이므로(4단계) 9¹³ = 2541865828329(약 2.54 × 10¹²) 이하입니다. 이것은 부호 없는 32비트의 최댓값 4294967295보다 크고, 2⁴¹ = 2199023255552 < 9¹³ < 2⁴² = 4398046511104이라 42비트가 필요합니다. 그래서 32비트 정수로는 부족합니다. 실제 창의 곱이 32비트를 넘는지는 수에 달려 있지만, 미리 알 수 없으니 상한으로 형을 정합니다.
• C++에서는 unsigned long long을 씁니다. C++ 표준은 이 형이 적어도 64비트임을 보장하므로 9¹³를 넉넉히 담습니다. 검산용 단순한 방법의 중간 곱도 숫자 k개 이하의 곱이라 같은 상한 안에 있습니다.
• Python의 int는 정밀도에 제한이 없어 넘칠 일이 없습니다.
• 인덱스와 Z는 std::size_t이고 n = 1000 이하입니다. Z는 창 안의 0만 세므로 0 아래로 내려가지 않습니다(빼는 0은 늘 창 안에 있던 0입니다).

C++17 구현

#include <cstddef>
#include <iostream>
#include <string>

// The 1000-digit number from the problem, 50 digits per line.
const std::string DIGITS =
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450";

// The value of the digit at position i of a string of '0'..'9'.
unsigned long long digit_at(const std::string& digits, std::size_t i) {
    return static_cast<unsigned long long>(digits[i] - '0');
}

// Largest product of k adjacent digits, for 1 <= k <= digits.size().
// Rolling window: zeros counts the zeros in the window and nonzero_product is the
// product of its other digits, so the window's product is 0 if zeros > 0 and
// nonzero_product otherwise. Only nonzero digits are ever divided out.
unsigned long long largest_product(const std::string& digits, std::size_t k) {
    unsigned long long nonzero_product = 1;
    std::size_t zeros = 0;
    unsigned long long best = 0;
    for (std::size_t i = 0; i < digits.size(); ++i) {
        if (i >= k) {
            // Remove the digit leaving the window before adding the new one,
            // so the window never holds more than k digits.
            const unsigned long long outgoing = digit_at(digits, i - k);
            if (outgoing == 0) {
                --zeros;
            } else {
                nonzero_product /= outgoing;
            }
        }
        const unsigned long long incoming = digit_at(digits, i);
        if (incoming == 0) {
            ++zeros;
        } else {
            nonzero_product *= incoming;
        }
        if (i + 1 >= k && zeros == 0 && nonzero_product > best) {
            best = nonzero_product;
        }
    }
    return best;
}

// Multiplies every window from scratch. Used only to cross-check largest_product.
unsigned long long largest_product_brute(const std::string& digits, std::size_t k) {
    unsigned long long best = 0;
    for (std::size_t start = 0; start + k <= digits.size(); ++start) {
        unsigned long long product = 1;
        for (std::size_t j = start; j < start + k; ++j) {
            product *= digit_at(digits, j);
        }
        if (product > best) {
            best = product;
        }
    }
    return best;
}

int main() {
    if (DIGITS.size() != 1000) {
        return 1;
    }
    for (const char c : DIGITS) {
        if (c < '0' || c > '9') {
            return 1;
        }
    }
    if (largest_product("3021945", 3) != 180 || largest_product("1020304", 3) != 0) {
        return 1;
    }
    if (largest_product(DIGITS, 4) != 5832) {
        return 1;
    }
    for (std::size_t k = 1; k <= 13; ++k) {
        if (largest_product(DIGITS, k) != largest_product_brute(DIGITS, k)) {
            return 1;
        }
    }
    std::cout << largest_product(DIGITS, 13) << '\n';
    return 0;
}

1000자리 수는 50자리씩 20줄로 나눠 썼습니다. 붙어 있는 문자열 리터럴은 컴파일할 때 하나로 이어집니다. 줄이 빠지거나 숫자가 잘못 옮겨졌을 때를 대비해 main이 먼저 길이가 1000인지, 모든 문자가 '0'–'9'인지 확인합니다.

작은 예는 셋입니다. “풀이 유도”에서 손으로 따라간 3021945(k = 3 → 180), 모든 창에 0이 들어 있어 답이 0이어야 하는 1020304(k = 3), 그리고 문제의 예(k = 4 → 5832)입니다. 이어서 k = 1부터 13까지 슬라이딩 윈도와 largest_product_brute(가장 단순한 방법)가 같은 값을 내는지 대조합니다. Z나 P를 고치는 순서, 나눗셈 조건, 창이 꽉 찼는지 보는 조건에 실수가 있다면 이 대조에서 걸립니다. 확인은 assert가 아니라 if와 return 1로 했습니다. assert는 NDEBUG가 정의된 빌드에서 아무 일도 하지 않기 때문입니다.

Python 3 구현

# The 1000-digit number from the problem, 50 digits per line.
DIGITS = (
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450"
)


def digit_at(digits: str, i: int) -> int:
    """The value of the digit at position i of a string of '0'..'9'."""
    return ord(digits[i]) - ord("0")


def largest_product(digits: str, k: int) -> int:
    """Largest product of k adjacent digits, for 1 <= k <= len(digits).

    Rolling window: zeros counts the zeros in the window and nonzero_product is the
    product of its other digits, so the window's product is 0 if zeros > 0 and
    nonzero_product otherwise. Only nonzero digits are ever divided out.
    """
    nonzero_product = 1
    zeros = 0
    best = 0
    for i in range(len(digits)):
        if i >= k:
            # Remove the digit leaving the window before adding the new one,
            # so the window never holds more than k digits.
            outgoing = digit_at(digits, i - k)
            if outgoing == 0:
                zeros -= 1
            else:
                nonzero_product //= outgoing
        incoming = digit_at(digits, i)
        if incoming == 0:
            zeros += 1
        else:
            nonzero_product *= incoming
        if i + 1 >= k and zeros == 0 and nonzero_product > best:
            best = nonzero_product
    return best


def largest_product_brute(digits: str, k: int) -> int:
    """Multiplies every window from scratch. Used only to cross-check largest_product."""
    best = 0
    for start in range(len(digits) - k + 1):
        product = 1
        for j in range(start, start + k):
            product *= digit_at(digits, j)
        if product > best:
            best = product
    return best


def main() -> None:
    if len(DIGITS) != 1000:
        raise SystemExit(1)
    for c in DIGITS:
        if c < "0" or c > "9":
            raise SystemExit(1)
    if largest_product("3021945", 3) != 180 or largest_product("1020304", 3) != 0:
        raise SystemExit(1)
    if largest_product(DIGITS, 4) != 5832:
        raise SystemExit(1)
    for k in range(1, 14):
        if largest_product(DIGITS, k) != largest_product_brute(DIGITS, k):
            raise SystemExit(1)
    print(largest_product(DIGITS, 13))


if __name__ == "__main__":
    main()

C++와 같은 알고리즘, 같은 확인입니다. 괄호 안에 이어 쓴 문자열 리터럴은 C++와 마찬가지로 하나로 합쳐집니다. 숫자 값은 C++의 c - '0'과 같은 뜻인 ord(c) - ord("0")으로 구하고, 나눗셈은 정확히 나누어떨어지는 경우에만 쓰므로 정수 나눗셈 //이 버리는 것은 없습니다. 작은 예가 틀리면 raise SystemExit(1)로 종료 코드 1을 냅니다. assert는 python -O로 실행하면 제거되므로 쓰지 않았습니다.

정답과 검증

인접한 13자리 숫자의 곱 중 최댓값은 23514624000입니다.

손으로 따라갈 수 있는 부분은 다음과 같습니다.

• 어느 창인가. 이 값을 내는 창은 1000자리 수의 왼쪽에서 198번째부터 210번째(1부터 셈)까지의 숫자 5576689664895입니다. 코드의 넷째 줄 끝 557과 다섯째 줄 처음 6689664895이고, 바로 다음 211번째 숫자는 0입니다.
• 곱. 이 숫자들은 5가 셋, 7이 하나, 6이 넷, 8이 둘, 9가 둘, 4가 하나이므로 곱은 5³ × 7 × 6⁴ × 8² × 9² × 4 = 125 × 7 × 1296 × 64 × 81 × 4 = 2¹² × 3⁸ × 5³ × 7이고, 계산하면 위의 값이 됩니다. 9¹³ 이하이고 32비트 최댓값보다 크므로 “복잡도”의 정수 범위 논의가 실제로 필요한 경우입니다.
• 더 큰 창이 없다는 손 점검(참고). 0이 든 창의 곱은 0이므로, 0으로 끊긴 구간 중 길이가 13 이상인 것만 보면 됩니다. 이 값에 이르려면 13개 숫자의 기하평균이 약 6.28 이상이어야 합니다. 숫자마다 9에 비해 모자라는 정도를 상용로그로 매기면(1은 약 0.95, 2는 약 0.65, 3은 약 0.48, 4는 약 0.35) 한 창에서 그 합이 약 2.03 이하여야 하므로, 1·2·3이 여럿 든 창은 금방 빠집니다. 그렇게 구간마다 따져 보면 위의 창만 남습니다. 다만 이것은 손 계산이라 실수할 수 있고, 결정적인 확인은 아래의 프로그램 검증입니다.

검증은 세 겹입니다.

1. 작은 예와 단순한 방법과의 대조. 두 프로그램 모두 답을 출력하기 전에 옮겨 넣은 수가 1000개의 숫자인지, 3021945(k = 3)가 180, 1020304(k = 3)가 0, 문제의 예(k = 4)가 5832인지 확인하고, k = 1부터 13까지 슬라이딩 윈도와 단순한 방법의 결과가 모두 같은지 확인합니다. 하나라도 다르면 0이 아닌 종료 코드로 끝납니다.
2. 두 구현의 일치. 이 시리즈의 저장소에서는 검사 스크립트가 C++ 코드를 g++ -std=c++17 -O2 -Wall -Wextra -Werror로 컴파일해 실행하고(경고도 실패로 처리), Python 코드를 python3 -I -B로 실행합니다. 두 출력이 저장해 둔 answer.txt와 바이트 단위로 같아야 하고, 0이 아닌 종료 코드나 시간 초과(C++ 1초, Python 10초)는 실패입니다. 시리즈 규칙상 이 검사를 통과한 코드만 글에 싣습니다.
3. 증명. 슬라이딩 윈도가 모든 창의 곱을 정확히 보고, 0으로 나누거나 나머지가 남는 나눗셈을 하지 않는다는 것은 “풀이 유도”와 “정확성 증명”에서 보였습니다.

경계 사례

• k = 1: 창은 숫자 하나이고 답은 가장 큰 숫자입니다. 나가는 숫자를 빼면 P는 1로 돌아갑니다(0이 아니면 d / d = 1, 0이면 Z만 바뀜). 프로그램의 대조가 k = 1을 포함합니다.
• 모든 창에 0이 있을 때: Z > 0인 창은 best를 바꾸지 않으므로 best는 시작값 0 그대로이고, 이것이 맞는 답입니다(1020304, k = 3).
• 0이 막 나가는 창: Z가 0으로 돌아오는 순간 P는 이미 창 안의 0이 아닌 숫자들의 곱이므로 그대로 창의 곱입니다. 따라가기의 i = 4가 이 경우입니다.
• k > n: 창이 하나도 없어 0을 돌려줍니다. 하지만 “창이 없다”와 “최대 곱이 0이다”를 구별하지 못하므로 함수는 k ≤ n을 전제로 둡니다.
• k = 0: 전제 밖입니다. i ≥ 0이 늘 참이라 아직 창에 넣지 않은 숫자를 빼게 되어 불변식이 깨집니다(C++에서는 그 숫자가 0이면 Z가 0 아래로 내려가 부호 없는 값이 돌아갑니다). 재사용한다면 입력을 먼저 확인해야 합니다.
• 빼고 넣는 순서: 넣고 나서 빼도 답은 같지만, 잠깐 k + 1개가 곱해져 상한이 9¹⁴로 커집니다. 이 글의 순서는 상한을 9ᵏ로 묶어 둡니다.

더 생각해 볼 것

• 더 긴 창. P ≤ 9ᵏ이므로 64비트 unsigned long long으로는 9²⁰(약 1.22 × 10¹⁹) < 2⁶⁴ − 1(약 1.84 × 10¹⁹) < 9²¹(약 1.09 × 10²⁰)에서 k ≤ 20까지가 안전합니다. 그보다 긴 창이라면 C++에서는 큰 정수를 직접 다루거나, 곱 대신 다른 비교 방법이 필요합니다.
• 로그의 합으로 비교하기. 곱의 대소는 log의 합의 대소와 같으므로 넘침 없이 창을 비교할 수 있습니다. 다만 부동소수점 오차 때문에 거의 같은 두 창을 잘못 비교할 수 있으니, 후보를 고른 뒤 정확한 정수 곱으로 다시 확인하는 편이 안전합니다.
• 나눗셈 없이. 스택 두 개로 만드는 큐에 각 스택의 누적 곱을 함께 저장하면, 나눗셈 없이 창의 곱을 유지할 수 있습니다. 되돌릴 수 없는 연산(예: 창 안의 최댓값)에도 그대로 통한다는 장점이 있습니다. 어떻게 하면 숫자 하나당 평균 상수 시간이 되는지 생각해 보세요.
• 곱 대신 합. 같은 문제를 곱 대신 합으로 물으면 0의 문제가 사라지고 빼기만으로 창을 밉니다. 곱에서는 0이 “되돌릴 수 없는 값”이라는 점이 이 글의 Z를 필요하게 만든 것입니다.

출처와 라이선스

• Project Euler, Problem 8 — 원래 문제. 이 글의 “문제” 절은 그 내용을 직접 요약한 것이고, 코드에 옮겨 넣은 1000자리 수도 원래 문제에서 가져온 것입니다. 이 부분들은 원문과 같은 CC BY-NC-SA 4.0으로 공유합니다. 문제의 저작자 표시는 Project Euler입니다.
• Project Euler, Copyright — 문제 본문의 라이선스와 링크 방식. 비영리 조건에 따라 이 글에는 광고를 싣지 않습니다(ads: false).
• Python의 int의 정밀도는 Numeric Types — int, float, complex, assert와 -O는 The assert statement를 따랐습니다. C++ 쪽의 사실(숫자 문자 '0'–'9'의 값이 차례로 1씩 커진다는 것, unsigned long long이 적어도 64비트라는 것, NDEBUG가 정의되면 assert가 아무 일도 하지 않는다는 것)은 C++ 표준(ISO/IEC 14882)의 규정입니다.
• 풀이, 증명, 코드는 직접 쓴 것입니다. Project Euler의 해설(overview), 포럼, 회원 전용 자료나 다른 풀이 사이트는 참고하지 않았습니다. Motitory는 Project Euler와 제휴나 후원 관계가 없고, Project Euler가 이 글을 검토하지도 않았습니다.