파도반 수열 정리

파도반 수열은 다음 점화식을 만족하는 수열이다.
$P(n) = P(n-2) + P(n-3)$ 형태로 주로 알려져 있으며,
초기값은 $P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2$로 정의한다.
또 다른 형태인 $P(n) = P(n-1) + P(n-5)$ 점화식으로도 같은 값이 나온다.
초기값만 동일하게 맞추면 어느 쪽을 써도 같은 수열이 된다는 점이 재미있다.

아래에서는 $P(n) = P(n-2) + P(n-3)$를 기준으로,
DP(동적 계획법) 방식과 전이 행렬(행렬 거듭제곱) 방식을 함께 보여준다.

1. DP 방식

DP는 배열을 이용해 차례대로 값을 채우는 직관적 방식이다.
시간 복잡도는 $O(n)$이지만, 구현이 간단하여 보통 문제 풀이에 적합하다.

def pado_dp(n):
    """
    P(n) = P(n-2) + P(n-3) 형태의 파도반 수열을
    동적 계획법으로 구하는 예시이다.
    초기값은 P(1)=1, P(2)=1, P(3)=1, P(4)=2, P(5)=2로 둔다.
    """
    dp = [0] * max(6, n+1)
    dp[1], dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2
    for i in range(6, n+1):
        dp[i] = dp[i-2] + dp[i-3]
    return dp[n]

if __name__ == "__main__":
    for i in range(1, 11):
        print(f"P({i}) = {pado_dp(i)}")

2. 전이 행렬 방식

선형 점화식은 상태 벡터와 전이 행렬로도 표현할 수 있다.
$P(n) = P(n-2) + P(n-3)$일 때, 상태 벡터를

$V(n) = \begin{bmatrix} P(n) \ P(n-1) \ P(n-2) \end{bmatrix}$

라 두면, 전이 행렬 $M$은

$$
\begin{bmatrix}
0 & 1 & 1 \cr
1 & 0 & 0 \cr
0 & 1 & 0
\end{bmatrix}
$$

이 된다.
이는 $V(n+1) = M \cdot V(n)$ 형태로 이어지며,
결국 $V(n) = M^{n-3} \cdot V(3)$로 일반화할 수 있다.
이를 코드로 구현한 예시는 다음과 같다.

def matmul(A, B):
    rA, cA = len(A), len(A[0])
    rB, cB = len(B), len(B[0])
    result = [[0]*cB for _ in range(rA)]
    for i in range(rA):
        for j in range(cB):
            s = 0
            for k in range(cA):
                s += A[i][k] * B[k][j]
            result[i][j] = s
    return result

def matpow(M, exp):
    size = len(M)
    I = [[int(i==j) for j in range(size)] for i in range(size)]
    result = I
    while exp > 0:
        if exp % 2 == 1:
            result = matmul(result, M)
        M = matmul(M, M)
        exp //= 2
    return result

def pado_matrix(n):
    if n in (1,2,3):
        return 1
    elif n in (4,5):
        return 2
    M = [
        [0,1,1],
        [1,0,0],
        [0,1,0]
    ]
    V3 = [
        [1],
        [1],
        [1]
    ]
    Mn = matpow(M, n-3)
    Vn = matmul(Mn, V3)
    return Vn[0][0]

if __name__ == "__main__":
    for i in range(1, 11):
        print(f"P({i}) = {pado_matrix(i)}")

3. 두 방식의 비교하면..

방식	시간 복잡도	구현 난이도	특징
DP	O(n)	낮음	간단명료, 공간 많이 사용
행렬	O(log n)	조금 높음	큰 n에 유리, 수학적 의미

DP는 배열 하나로 간단히 해결할 수 있으며, 문제에서 요구하는 범위가 그리 크지 않으면 편리하다.
행렬 거듭제곱은 지수 시간 단축이 가능하고, $n$이 매우 클 때 더 빠르게 계산할 수 있다.