7288 : 재귀 탑 쌓기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
높이 $N$인 탑을 쌓는 방법의 수를 구하십시오.
블록 타입: 높이 1짜리 블록과 높이 2짜리 블록을 조합하여 정확히 높이 $N$을 만드는 경우의 수입니다.
이 문제는 타일링 문제와 동일하며, 점화식은 피보나치 수열과 같습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
블록 타입: 높이 1짜리 블록과 높이 2짜리 블록을 조합하여 정확히 높이 $N$을 만드는 경우의 수입니다.
이 문제는 타일링 문제와 동일하며, 점화식은 피보나치 수열과 같습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 탑의 높이 $N$이 주어집니다. ($1 \le N \le 50$)
출력 설명
높이 $N$인 탑을 쌓는 방법의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
$f(1) = 1$, $f(2) = 2$, $f(n) = f(n-1) + f(n-2)$. 재귀 + 메모이제이션으로 구현하십시오.