boj9095
-
[Algo Rhythm🕺💃] BOJ 9095 - 1, 2, 3 더하기Algo Rhythm🕺💃/BOJ 2021. 6. 29. 00:06
💫문제 분석 테스트 케이스의 개수를 $t$, 각 테스트 케이스마다 주어지는 정수를 $n (1 \le n \lt 11)$이라고 하자. 그리고 $n$을 $1,\ 2, \ 3$의 합으로 나타내는 방법의 수를 $f(n)$이라고 하자. 각 테스트케이스마다 $f(n)$을 출력해야 하며, 합을 나타낼 때는 수를 1개 이상 사용해야 한다. $f(n)$은 1부터 차례대로 아래와 같다. 이때 파란색 동그라미로 표시된 수들을 관찰하면 분명히 연쇄적인 관계가 있다는 것을 알 수 있다. 따라서 이 문제는 그 '연쇄적인 관계'를 이용하여 해결할 수 있다. 🔥문제 풀이 앞서 언급한 연쇄적인 관계는 다음과 같다. $\begin{matrix} f(i) &=& \sum_{j = 1}^3 g(i, j) & (1\le i\lt 11, i ..