[LeetCode] 2906 Construct Product Matrix (C/C++)

문제

https://leetcode.com/problems/construct-product-matrix

풀이

시간 초과를 피하기 위한 기본 아이디어

기본 아이디어는 간단하다. 칸의 개수는 최대 $10^5$ 개 이므로, 단순히 각 칸에 대해 나머지 모든 칸의 곱을 계산하는 방식은 최대 $10^{10}$ 으로 약 100억 번의 연산이 필요하므로, 시간 초과가 발생한다. 따라서 모든 칸의 곱을 구한 후, 각 칸의 값을 나누는 방식으로 접근하면 최대 $10^5$ 번의 곱셈과 최대 $10^5$ 번의 나눗셈으로 총 $2 \cdot 10^5$ 으로 약 20만 번의 연산으로 문제를 해결할 수 있다.

모듈러 연산

이 문제를 포함한 많은 문제들에서 최종 결과 값이 매우 커질 수 있으므로 자료형 오버플로우를 방지하기 위해 모듈러 연산 결과를 반환하도록 요구한다.

개인적으로 평소에 별 생각 없이 매 반복마다 모듈러 연산을 적용하고, 해당 결과가 최종 값에서만 모듈러 연산을 적용한 값과 같다는 성질을 이용했었는데, 그 원리를 깊이 생각하지 않으면서 사용하곤 한다. 이 문제에서도 각 칸을 순회하며 값을 곱하고 모듈러 연산으로 구한 나머지를 누적하고 마지막에 해당 칸의 값을 나눠서 최종 결과를 구하는 방식으로 접근했는데, 이 문제에서 해당 방식은 올바른 결과를 보장하지 않는다.

우선 기본적인 모듈러 연산부터 알아보자. $a$ 를 $m$ 으로 나눈 나머지가 $b$ 라는 것은, $a - b$ 가 $m$ 의 정수배라는 의미다.

a \bmod m = b \iff a - b = k \cdot m \quad (k \in \mathbb{Z})

모듈러 연산의 성질

모듈러 연산은 아래 3가지 특징을 가진다.

$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
$(a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m$
$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$

즉, 모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 분배법칙, 결합법칙, 교환법칙을 만족한다.

이를 증명해보자.

우선, $a$ 를 $m$ 으로 나눈 나머지가 $a \bmod m$ 이고 $b$ 를 $m$ 으로 나눈 나머지가 $b \bmod m$ 이므로,
$a = k \cdot m + (a \bmod m), \quad b = l \cdot m + (b \bmod m)$
으로 표현할 수 있다.
덧셈 법칙에 대해,
$(a + b) \bmod m = ((k + l) \cdot m + (a \bmod m) + (b \bmod m)) \bmod m$
이고, $(k + l) \cdot m$ 은 $m$ 의 정수배이므로,
$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
이 성립함을 알 수 있다.
뺄셈은 음수를 더하는 것과 동일하므로, $(a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m$ 도 성립한다.
곱셈 법칙에 대해,
$\begin{aligned} (a \cdot b) \bmod m &= ((k \cdot l) m^2 \\ &\quad + (k(b \bmod m) + l(a \bmod m)) m \\ &\quad + (a \bmod m)(b \bmod m)) \bmod m \end{aligned}$
이고, $(k \cdot l) \cdot m^2$ 과 $(k \cdot (b \bmod m) + l \cdot (a \bmod m)) \cdot m$ 은 모두 $m$ 의 정수배이므로,
$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$
이 성립함을 알 수 있다.

모듈러 연산의 성질과 반복문

모듈러 연산은 위 성질들을 만족하기 때문에, 반복문에서 결과를 누적할 때마다 모듈러 연산을 적용해도 최종 결과에 모듈러 연산을 적용한 값과 같다는 것을 보장한다.

지수(Exponentiation) 계산에서의 응용:

$a^n$ 을 계산할 때, 매 곱셈마다 모듈러 연산을 적용하면, 최종 결과에 모듈러 연산을 적용한 값과 같다.
$(a^n) \bmod m = ((a \bmod m)^n) \bmod m$
예를 들어 17^5를 11로 나눈 나머지를 계산할 때, 매 곱셈마다 모듈러 연산을 적용하면 다음과 같다.
$\begin{aligned} 17^1 &= 17 \equiv 6 \pmod{11} \\ 17^2 &= 17 \cdot 17 \equiv 6 \cdot 6 = 36 \equiv 3 \pmod{11} \\ 17^3 &= 17^2 \cdot 17 \equiv 3 \cdot 6 = 18 \equiv 7 \pmod{11} \\ 17^4 &= 17^3 \cdot 17 \equiv 7 \cdot 6 = 42 \equiv 9 \pmod{11} \\ 17^5 &= 17^4 \cdot 17 \equiv 9 \cdot 6 = 54 \equiv 10 \pmod{11} \end{aligned}$
$17^5 = 1,419,857$ 이고, $1,419,857 \bmod 11 = 10$ 이므로, 매 곱셈마다 모듈러 연산을 적용한 결과와 최종 결과에 모듈러 연산을 적용한 값이 같음을 알 수 있다.
반복문에서의 응용:

$n$ 개의 수 $a_1, a_2, ..., a_n$ 의 곱을 계산할 때, 매 곱셈마다 모듈러 연산을 적용하면, 최종 결과에 모듈러 연산을 적용한 값과 같다.
$(a_1 \cdot a_2 \cdot ... \cdot a_n) \bmod m = ((a_1 \bmod m) \cdot (a_2 \bmod m) \cdot ... \cdot (a_n \bmod m)) \bmod m$
예를 들어, $3$ , $5$ , $7$ 의 곱을 11로 나눈 나머지를 계산할 때, 매 곱셈마다 모듈러 연산을 적용하면 다음과 같다.
$\begin{aligned} 3 &\equiv 3 \pmod{11} \\ 3 \cdot 5 &\equiv 3 \cdot 5 = 15 \equiv 4 \pmod{11} \\ 3 \cdot 5 \cdot 7 &\equiv 4 \cdot 7 = 28 \equiv 6 \pmod{11} \end{aligned}$
$3 \cdot 5 \cdot 7 = 105$ 이고, $105 \bmod 11 = 6$ 이므로, 매 곱셈마다 모듈러 연산을 적용한 결과와 최종 결과에 모듈러 연산을 적용한 값이 같음을 알 수 있다.

모듈러 연산과 나눗셈

위에서 살펴보았듯이, 모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 분배법칙, 결합법칙, 교환법칙에 대해 닫혀있지만, 나눗셈에 대해서는 닫혀있지 않다.

즉,

(a / b) \bmod m \neq (a \bmod m) / (b \bmod m) \quad (b \mid a, \; b \bmod m \mid a \bmod m)

이다.

반례를 통해 살펴보자. $a = 10$ , $b = 2$ , $m = 6$ 인 경우를 생각해보자.

\begin{aligned} (a / b) \bmod m &= (10 / 2) \bmod 6 \\ &= 5 \bmod 6 \\ &= 5 \end{aligned}

\begin{aligned} (a \bmod m) / (b \bmod m) &= (10 \bmod 6) / (2 \bmod 6) \\ &= 4 / 2 \\ &= 2 \end{aligned}

따라서, $(a / b) \bmod m \neq (a \bmod m) / (b \bmod m)$ 이므로, 모듈러 연산과 나눗셈은 닫혀있지 않음을 알 수 있다.

결론

즉, 문제에서 모든 칸의 곱을 구할 때 나머지 연산을 적용하고 간 칸의 값을 나눌 때도 나머지 연산을 적용하는 방식으로 접근하면, 최종 결과에 나머지 연산을 적용한 값과 같다는 것을 보장할 수 없으므로, 올바른 결과를 얻을 수 없다. (더 정확하고 자세한 내용은 모듈러 합동과 역원에 대해 알아보면 좋을 것 같다.)

$a_i$ 의 값은 처음부터 자신 앞 칸까지의 곱인 $a_0 \cdot a_1 \cdot ... \cdot a_{i-1}$ 과 자신 이후부터 끝 칸까지의 곱인 $a_{i+1} \cdot a_{i+2} \cdot ... \cdot a_{n-1}$ 의 곱과 같다. 이 성질을 이용해서 prefix, suffix 곱을 구한 후 각 칸의 값을 prefix 곱과 suffix 곱의 곱으로 구하는 방식으로 접근해야 한다. 이는, 곱셈에 대한 모듈러 연산이 적용되므로 최종 결과에 모듈러 연산을 적용한 값과 같다는 것이 보장된다.

정답 코드

C++17

class Solution {
private:
    using Matrix = std::vector<std::vector<int>>;
    static constexpr int MOD = 12345;

public:
    Matrix constructProductMatrix(const Matrix &matrix) {
        const size_t N = matrix.size();
        const size_t M = matrix[0].size();
        const size_t total = N * M;
        Matrix ret(N, std::vector<int>(M, 1));

        long long suffix = 1;
        for (size_t index = 0; index < total; index++) {
            const int r = (total - 1 - index) / M;
            const int c = (total - 1 - index) % M;

            ret[r][c] = static_cast<int>(suffix);
            suffix = (suffix * matrix[r][c]) % MOD;
        }

        long long prefix = 1;
        for (size_t index = 0; index < total; index++) {
            const int r = index / M;
            const int c = index % M;

            ret[r][c] = static_cast<int>(ret[r][c] * prefix % MOD);
            prefix = (prefix * matrix[r][c]) % MOD;
        }

        return ret;
    }
};