erick12   1년 전

그림으로부터 점화관계 $P(n)=P(n-1)+P(n-5)$ $(\text{단, } P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2)$ 를 얻어 낼 수 있습니다.

수학적 귀납법으로 $P(n)=P(n-2)+P(n-3)$을 증명해봅시다.

$(1)$ $n \le 5$일 때
초항에 의해 성립합니다.

$(2)$ $k$ 이하의 $n$에서 성립함을 가정하면

$n = k+1$에서

\[
\begin{aligned}
P(k+1) &= P(k) + P(k-4) \\
&= P(k-1) + P(k-5) + P(k-4) \\
&= P(k-1) + P(k-2) \quad \text{($n = k-2$에서 성립함을 이용)}
\end{aligned}
\]

따라서 3 이상의 모든 n에 대해 $P(n)=P(n-2)+P(n-3)$ $(\text{단, } P(1)=P(2)=P(3)=1)$이 성립합니다.

이제 이 점화식의 일반해를 구합시다.

특성방정식은 $x^{3}-x-1=0$입니다.

카르다노의 공식으로 세 특성근을 구하면 다음과 같습니다.

\[
\begin{cases}
x = \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[2mm]
x = \omega \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega^2 \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[1mm]
x = \omega^2 \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},
\end{cases}
\]

여기서 $\omega = \dfrac{-1+\sqrt{3}i}{2}$입니다.

세 근을 순서대로 $a, b, c$라고 둡시다. ($a$가 실근입니다)

$P(n) = A a^n + B b^n + C c^n$가 됩니다.

$n$에 $1, 2, 3$을 대입하면

\[
\begin{cases}
A a + B b + C c = 1,\\
A a^2 + B b^2 + C c^2 = 1,\\
A a^3 + B b^3 + C c^3 = 1
\end{cases}
\]

크래머 공식으로 이걸 풀면

\[
\begin{cases}
A &= \frac{(1-b)(1-c)}{a(a-b)(a-c)}, \\
B &= \frac{(1-c)(1-a)}{b(b-c)(b-a)}, \\
C &= \frac{(1-a)(1-b)}{c(c-a)(c-b)}
\end{cases}
\]

이걸 대입하면

\[
P(n) = \displaystyle\sum_{\text{cyc}} \frac{a^{\,n-1} (1-b)(1-c)}{(a-b)(a-c)}
\]

$a, b, c$에 세 근을 대입하면

\[
\begin{aligned}
P(n) &=
\dfrac{
\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
} \\[1mm]
&+
\dfrac{
\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)
} \\[1mm]
&+
\dfrac{
\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)
}
\end{aligned}
\]

와 같이 됩니다.

이제 여기에 $n$을 대입하면 됩니다.

실수 오차가 생기므로 허수부분을 없애고 실수부분에 round를 하면 됩니다.

erick12   1년 전

참고로 저는 이렇게 푸느니 DP로 풀었습니다.

muyeong_kim   1년 전

행렬을 이용해보는것도 좋을것 같습니다

https://www.acmicpc.net/proble...

erick12   1년 전

피보나치는 외우고 있습니다만

$\dfrac{1}{\sqrt{5}}\Bigl(\Bigl(\dfrac{1+\sqrt{5}}{2}\Bigr)^{n}-\Bigl(\dfrac{1-\sqrt{5}}{2}\Bigr)^{n}\Bigr)$ 


muyeong_kim   1년 전

일반항을 이용하면 분할정복을 이용해 O(log n)으로 풀수있지만 계산이 복잡하므로 행렬을 이용하면 똑같은 시간복잡도로 풀수있습니다 공부해보시면 도움이 되실것같아서 링크는 연습문제로 남긴것입니다

erick12   1년 전

저는 삼차방정식 문제 근의공식으로 푼 사람입니다 ㅋㅋㅋ

erick12   1년 전

수식 오류 좀 고쳤습니다

댓글을 작성하려면 로그인해야 합니다.