6000 : 타일링 — 메모이제이션 기초

시간 2.000s · 메모리 256MB · 제출 2 · 정답 2

코드제출 문제 풀기

채점기록 통계 묻고답하기

$2 \times n$ 크기의 격자판을 $1 \times 2$ (또는 $2 \times 1$) 크기의 타일로 채우는 방법의 수를 구하십시오.

단, 순수 반복문이 아닌 재귀 함수와 메모이제이션(Top-down DP) 방식을 이용하여 해결하십시오.

[제약 조건]
• $n$: $1 \le n \le 100$ (정수)
• 파이썬에서는 매우 큰 정수도 오버플로 없이 자동으로 지원하므로 정수 원본을 그대로 출력합니다.

첫째 줄에 정수 $n$이 주어집니다.

[제약 조건]
• $1 \le n \le 100$

$2 \times n$ 크기의 직사각형을 $2 \times 1$ 타일로 채우는 경우의 수를 출력합니다.

피보나치 수열 $DP[n] = DP[n-1] + DP[n-2]$ 점화식을 따르며, 파이썬에서는 정수 오버플로 없이 큰 수를 자동 지원합니다. (예: sys.stdin 활용)