7041 : 반복문 피보나치 함수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
피보나치 수 $F(n)$은 다음과 같이 정의됩니다.
- $F(0) = 0$
- $F(1) = 1$
- $F(n) = F(n-1) + F(n-2)$ ($n \ge 2$)
여러 개의 인덱스 k가 주어질 때, 각 k에 대해 $F(k)$를 구하는 프로그램을 작성하십시오.
[주의] 이 문제는 재귀 함수(Recursion)를 사용할 경우 시간 초과 또는 메모리 초과가 발생할 수 있습니다. 반드시 반복문(Iterative)을 사용하여 피보나치 수를 계산하십시오. 재귀 함수를 사용해 호출을 진행할 경우 감점(오답 처리)될 수 있습니다.
[제약 조건]
• 각 인덱스 $k$: $0 \le k \le 80$
- $F(0) = 0$
- $F(1) = 1$
- $F(n) = F(n-1) + F(n-2)$ ($n \ge 2$)
여러 개의 인덱스 k가 주어질 때, 각 k에 대해 $F(k)$를 구하는 프로그램을 작성하십시오.
[주의] 이 문제는 재귀 함수(Recursion)를 사용할 경우 시간 초과 또는 메모리 초과가 발생할 수 있습니다. 반드시 반복문(Iterative)을 사용하여 피보나치 수를 계산하십시오. 재귀 함수를 사용해 호출을 진행할 경우 감점(오답 처리)될 수 있습니다.
[제약 조건]
• 각 인덱스 $k$: $0 \le k \le 80$
입력 설명
첫째 줄에 인덱스 $k$가 주어집니다. ($0 \le k \le 80$)
출력 설명
$k$번째 피보나치 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
재귀를 사용하면 중복 연산으로 인해 $O(2^N)$의 시간이 걸리지만, 변수 두 개를 이용해 값을 갱신하는 반복문을 사용하면 $O(N)$으로 k=80까지의 피보나치 수도 1초 내에 안전하게 구할 수 있습니다.