[바미] n제곱 계산

 

문제

https://www.acmicpc.net/problem/12728

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

const lines = input.split('\n');
const T = parseInt(lines[0]);

const mod = 1000; // 마지막 세 자리를 구하기 위해 모듈러 1000 사용
const period = 1500; // Sₙ 모듈러 1000의 주기

// Sₙ 모듈러 1000을 저장할 배열 생성
const S_arr = new Array(period);
S_arr[0] = 2; // S₀ = 2
S_arr[1] = 6; // S₁ = 6

// 주기 내의 모든 Sₙ 모듈러 1000 값 계산
for (let n = 2; n < period; n++) {
    // 점화식을 이용하여 Sₙ 계산
    S_arr[n] = (6 * S_arr[n - 1] - 4 * S_arr[n - 2]) % mod;
    // 음수 결과를 피하기 위해 모듈러 연산 후 양수로 변환
    if (S_arr[n] < 0) S_arr[n] += mod;
}

// 각 테스트 케이스 처리
for (let t = 1; t <= T; t++) {
    const n = parseInt(lines[t]);
    const index = n % period; // 주기를 이용하여 인덱스 계산
    const S_n_mod = S_arr[index]; // 해당 n에 대한 Sₙ 모듈러 1000 값

    // (3 + √5)ⁿ의 정수 부분은 Sₙ - 1
    let integerPart = (S_n_mod - 1 + mod) % mod;
    // 결과를 세 자리로 맞추기 위해 앞에 0을 추가
    integerPart = integerPart.toString().padStart(3, '0');
    // 형식에 맞게 출력
    console.log(`Case #${t}: ${integerPart}`);
}

문제 해설

이번 문제는 정말 역대급으로 어려웠습니다. 평소에 다루지 않던 수학적인 개념을 코드에 녹여내야 하는 문제이기 때문인데요.

 

주어진 문제는 (3 + √5)ⁿ의 소수점 앞의 마지막 세 자리를 구하는 것인데 여기서 n은 최대 2,000,000,000까지 갈 수 있죠.

 

주어진 예제는 아래와 같아요.

n = 5일 때, (3 + √5)⁵ ≈ 3935.73982... 이므로, 답은 935입니다.

n = 2일 때, (3 + √5)² ≈ 27.4164079... 이므로, 답은 027입니다.

 

따라서 (3 + √5)ⁿ의 소수점 앞의 마지막 세 자리를 효율적으로 계산하는 알고리즘을 만들어야 합니다만  여기서 n은 매우 큰 수가 될 수 있으므로, 직접 계산하는 것은 현실적이지 않기 때문에 수반수(conjugate) 개념을 활용하여 수열 Sn을 정의 할 수 있게 됩니다.

❗ 수반수
서로 나눌 수 있는 두 수의 관계에서 상대되는 쪽을 이르는 말입니다.
두 수 (a + √b)와 (a - √b)는 수반수이며, 이들의 합과 곱은 유리수 또는 정수가 됩니다.

 

따라서  (3 + √5)와 (3 - √5)가 서로 수반수(conjugate)이기 때문에 \[S_n = (3 + \sqrt{5})^n + (3 - \sqrt{5})^n\] 으로 정의 할 수 있습니다.

이 때 Sn은 항상 정수가 되는데 그 이유는 (3 + √5)ⁿ과 (3 - √5)ⁿ은 수반수이고, 이들의 합은 무리수가 사라져서 정수가 되기 때문입니다.

 

그 다음 (3 - √5)는 약 0.763...인 실수이며, n이 커질수록 (3 - √5)ⁿ은 0에 가까워지게 되는데 따라서 (3 + √5)ⁿ ≈ Sₙ - (3 - √5)ⁿ ≈ Sₙ - ε (ε는 매우 작은 값)이 되고,  (3 + √5)ⁿ의 정수 부분은 Sₙ - 1과 거의 같습니다.

 

따라서 Sₙ은 아래의 점화식을 만족하게 됩니다.

❗ 점화식
수열의 각 항을 이전 항들을 이용하여 표현하는 관계식.

 

\[S_n = 6S_{n-1} - 4S_{n-2}\]

이 때 초기 값은 S₀ = 2, S₁ = 6이 되고, 이 점화식을 사용하면 Sₙ을 빠르게 계산할 수 있게 됩니다.

 

그리고 이 문제에선 마지막 세 자리 숫자를 원하기 때문에 계산 중에 수가 커지는 것을 방지하기 위해 모듈러 1000을 사용하였습니다.

하지만 모듈러 연산을 점화식에 직접 적용하면 수열의 성질이 변할 수 있으므로 주의해야 합니다.

 

그리고 모듈러 연산을 적용한 수열은 주기가 생기며, 이 주기를 이용하여 계산을 최적화할 수 있습니다.

먼저 Sₙ을 모듈러 1000로 계산할 때, 수열은 일정한 주기를 가지게 됩니다. 실제로는 Sₙ 모듈러 1000의 주기는 1500이 됩니다.

따라서, Sₙ mod 1000은 n을 1500으로 나눈 나머지에 따라 반복하게 되고, 이 성질을 이용하여 Sₙ mod 1000을 효율적으로 계산할 수 있게 되는 것이죠.

풀이 과정

여기까지 잘 따라오셨죠? 본격적으로 이 알고리즘의 구체적인 풀이 과정을 설명해드리겠습니다.

 

먼저 수열 Sₙ mod 1000을 미리 계산해줍니다. 주기가 1500이므로, n = 0부터 1499까지의 Sₙ mod 1000을 미리 계산하여 배열에 저장하죠.

 

이 때 점화식을 이용하여 각 Sₙ을 계산하게 되는데 이 때 계산식은 

\[ S_n = (6 \times S_{n-1} - 4 \times S_{n-2}) \mod 1000 \] 이렇게 되있는데 음수 결과를 피하기 위해, 계산 후에 모듈러 연산을 수행한 것으로 이해하시면 됩니다.

 

그 후 입력된 n에 대해 Sₙ mod 1000 찾게 됩니다. 

먼저, 각 테스트 케이스마다 주어진 n에 대해, n을 1500으로 나눈 나머지를 구합니다.

\[ \text{index} = n \mod 1500 \]

 

그 다음 미리 계산한 배열에서 Sₙ mod 1000 값을 가져옵니다.

\[ S_n \mod 1000 = S_{\text{index}} \]

 

이제 여기까지 계산이 끝났다면 (3 + √5)ⁿ의 정수 부분을 계산하게 됩니다.

(3 + √5)ⁿ의 정수 부분은 Sₙ - 1과 거의 같으므로 아래와 같은 계산식으로 계산되게 됩니다.

\[ \text{integerPart} = (S_n - 1) \mod 1000 \]

그 다음 음수 결과를 방지하기 위해 모듈러 연산을 적용해줍니다.

\[ \text{integerPart} = (S_n - 1 + 1000) \mod 1000 \]

 

여기까지 계산이 끝났다면 마지막으로 소수점 앞의 숫자가 세 자리보다 작으면 앞에 0을 추가하여 세 자리로 만들어 결과 출력 형식을 맞춰줍니다. 

 

그래서 integerPart가 27이면 "027"로 출력하게 되죠.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

수열 Sₙ 모듈러 1000의 주기 계산과 각 테스트 케이스 처리의 시간 복잡도를 계산하면 됩니다.

 

먼저 수열 Sₙ 모듈러 1000의 주기 계산의 경우 주기(period)는 1500이 되고,  n = 0부터 1499까지의 Sₙ mod 1000을 미리 계산하여 배열에 저장합니다.

 

이 부분의 시간 복잡도는 O(period)이며, 여기서 period = 1500이기 때문에 O(1500)가 됩니다.
각 항을 계산할 때 상수 시간 작업을 수행하므로, 전체 계산은 O(1500)이 됩니다.

 

그 다음 각 테스트 케이스 처리 부분을 볼까요? 테스트 케이스의 수를 T라고 하면, 각 테스트 케이스마다 동작하는 것은 다음과 같습니다.

 

• n을 period로 나눈 나머지를 계산 - O(1)
• 미리 계산한 배열에서 해당 인덱스의 값을 가져옴 - O(1)
• 간단한 산술 연산 및 문자열 처리 - O(1)

따라서 각 테스트 케이스마다 O(1)의 시간이 소요된다는 것을 알 수 있고, 전체 테스트 케이스에 대한 시간 복잡도는 O(T)가 됩니다

그래서 전체 알고리즘의 시간 복잡도는 두 부분을 합친 O(period + T)가 되며, 여기서 period는 상수(1500)이므로 O(T)로 볼 수 있게도됩니다. 이  문제 제한 조건에서 T는 최대 100입니다.

 

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

이를 계산하기 위해서는  수열 Sₙ 모듈러 1000의 저장을 위한 배열과 기타 변수 및 상수 공간을 계산하면 됩니다.

 

먼저 수열 Sₙ 모듈러 1000의 저장을 위한 배열을 보겠습니다. 배열의 크기는 period에 따라 결정되며, 크기는 1500이 되고, 이 부분의 공간 복잡도는 자연스럽게 O(period)이 되기 때문에 O(1500)이 됩니다.

 

그 다음 기타 변수 및 상수 공간을 살펴보죠. 입력을 저장하기 위한 변수들(T, lines 등)은 입력 크기에 비례하지만, T가 최대 100이므로 상수입니다.

그리고 기타 각종 변수들(n, index, S_n_mod, integerPart 등)도 상수 공간을 사용하게 됩니다.

 

주요 공간 사용은 수열 저장을 위한 배열이기 때문에 전체 공간 복잡도는 O(period)인데 여기서 period는 상수이기 때문에 공간 복잡도 역시 O(1)로 볼 수 있습니다.

---

 

추가 설명

행렬을 이용한 점화식 계산

점화식을 행렬 형태로 표현하면, 빠른 거듭제곱을 이용하여 Sₙ을 효율적으로 계산할 수 있는데요.
행렬 M을 다음과 같이 정의 할 수 있습니다.

\[ M = \begin{pmatrix} 6 & -4 \\ 1 & 0 \end{pmatrix} \]

 

그렇게 되면 아래와 같은 식이 성립됩니다.

\[ \begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = M \times \begin{pmatrix} S_{n-1} \\ S_{n-2} \end{pmatrix} \]

 

이것을 반복하면 아래와 같은 식이 만들어지게 됩니다.

\[ \begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = M^{n-1} \times \begin{pmatrix} S_1 \\ S_0 \end{pmatrix} \]

 

이 처럼 행렬의 거듭제곱은 이진 거듭제곱 방법을 사용하여 O(log n)의 시간 복잡도로 계산할 수 있게 됩니다.

모듈러 연산 시 음수 처리

프로그래밍 언어에서 음수를 모듈러 연산하면 음수가 나올 수 있기 때문에 음수 결과를 양수로 변환해야 할 필요가 있습니다.

 

예를 들어 -4% 1000은 -4이기 때문에 이를 양수로 만들기 위해 아래와 같이 처리해줘야 하죠.

\[ ((-4 \mod 1000) + 1000) \mod 1000 = 996 \]