[백준] 27435번 - 파도반 수열 2 [Java]

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

 

[백준] 27435번 - 파도반 수열 2 [Java]

---

1.  아이디어

 

파도반 수열 문제에서 N의 범위가 매우 커진 문제로 이전과 달리 거듭제곱의 분할 정복과 점화식의 행렬 변환으로 해결해야 한다.([코딩테스트 준비/백준] - [백준] 9461번 - 파도반 수열 [Java])

---

2. 문제풀이

 

일단 해당 문제를 풀기 위해서 점화식을 행렬로 표현할 수 있어야 한다.

파도반 수열은 a(n) = a(n-2) + a(n-3)의 점화식을 갖는데 이를 다음과 같이 행렬의 거듭제곱으로 표현할 수 있다.

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}a_{n-2}+a_{n-3}\\ a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}0&1&1\\ 1&0&0\\ 0&1&0\end{pmatrix} \begin{pmatrix}a_{n-1}\\ a_{n-2}\\ a_{n-3}\end{pmatrix}$

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}0&1&{}1\\ 1&0&0\\ 0&1&0\end{pmatrix} \begin{pmatrix}a_{n-1}\\ a_{n-2}\\ a_{n-3}\end{pmatrix} =\begin{pmatrix}0&1&1\\ 1&0&0\\ 0&1&0\end{pmatrix}^{2} \begin{pmatrix}a_{n-2}\\ a_{n-3}\\ a_{n-4}\end{pmatrix} =\begin{pmatrix}0&1&1\\ 1&0&0\\ 0&1&0\end{pmatrix}^{3} \begin{pmatrix}a_{n-3}\\ a_{n-4}\\ a_{n-5}\end{pmatrix}$

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}0&1&1\\ 1&0&0\\ 0&1&0\end{pmatrix}^{n-3} \begin{pmatrix}a_{3}\\ a_{2}\\ a_{1}\end{pmatrix}$

 

a1, a2, a3는 문제의 그림과 같이 모두 1이므로 저 행렬의 거듭제곱만 빠르게 구하면 해결할 수 있다.

 

거듭제곱은 선형적으로 구하기에는 시간이 너무 많이 걸리므로 절반씩 나누어 곱하는 분할정복으로 O(log N)으로 해결할 수 있다.

 

구현은 정답을 출력하는 solve 메서드를 호출하고 solve 메서드가 행렬의 거듭제곱을 반환하는 recur 메서드를 호출해서 정답을 반환하도록 했다. recur 메서드는 N이 1이면 기본 행렬을 반환하고 1이 아닐 경우 짝수면 N/2 거듭제곱인 두 행렬의 곱을, 홀수면 N/2와 N/2+1 거듭제곱인 두 행렬의 곱을 반환하도록 했다. 두 행렬의 곱은 mul 메서드에서 구현했다.

---

3. 코드

 

import java.io.*;

public class Main {

    // 점화식의 기본 행렬
    private static final long[][] baseMatrix = {
            {0, 1, 1},
            {1, 0, 0},
            {0, 1, 0}
    };

    private static final int MOD = 998_244_353;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            long N = Long.parseLong(br.readLine());
            sb.append(solve(N)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static long solve(long N) {
        if (N <= 3) return 1;

        long[][] matrix = recur(N - 3);

        // a1 = 1, a2 = 1, a3 = 1
        return (matrix[0][0] + matrix[0][1] + matrix[0][2]) % MOD;
    }

    // 행렬의 거듭제곱을 반환하는 메서드
    private static long[][] recur(long N) {
        if (N == 1) return baseMatrix;

        long[][] half = recur(N / 2);

        if (N % 2 == 0) return mul(half, half);
        else return mul(half, mul(half, baseMatrix));
    }

    // 두 행렬의 곱을 반환하는 메서드
    private static long[][] mul(long[][] matrix1, long[][] matrix2) {
        long[][] ans = new long[3][3];

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ans[i][j] += (matrix1[i][k] * matrix2[k][j]) % MOD;
                }
            }
        }

        return ans;
    }

}

---

4. 후기