6001 : 계단 오르기 — 메모이제이션

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

코드제출 문제 풀기

채점기록 통계 묻고답하기

총 $n$개의 계단이 있습니다. 한 번에 $1$계단 또는 $2$계단씩 오를 수 있을 때, 꼭대기에 도달하는 방법의 수를 구하십시오.

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

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

첫째 줄에 계단의 수 $n$이 주어집니다.

[제약 조건]
• $1 \le n \le 1{,}000$

$n$번째 계단에 도달할 수 있는 모든 경우의 수를 출력합니다.

한 번에 1계단 또는 2계단을 오를 수 있으므로 $DP[n] = DP[n-1] + DP[n-2]$의 피보나치 점화식이 성립합니다. 입력은 sys.stdin을 통해 EOF까지 처리합니다.