반응형
14495번: 피보나치 비스무리한 수열 (acmicpc.net)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
| 2초 | 512MB | 1865 | 1002 | 909 | 55.630% |
문제
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.
1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...
자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!
입력
자연수 n(1<=n<=116)이 주어진다.
출력
n번째 피보나치 비스무리한 수를 출력한다.
예제 입력 1
10
예제 출력 1
19
풀이
다이나믹 프로그래밍을 이용한 '피보나치 수 7' 문제와 동일합니다.
차이점이라고는 배열의 1~3번 인덱스에 1을 저장 한 후 n번까지 반복을 하면 된다는 점 뿐입니다.
(참고)
2021.03.10 - [백준] - [백준 BOJ 15624번] 피보나치 수 7 (C / C++ ) [DP, 다이나믹 프로그래밍]
코드
|
1
2
3
4
5
6
7
8
9
|
// 피보나치 비스무리한 수열
#include <iostream>
long long f[117]={0,1,1,1};
int main(){
int n;
std::cin>>n;
for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-3];
std::cout<<f[n];
}
|
cs |
14495번: 피보나치 비스무리한 수열 (acmicpc.net)
14495번: 피보나치 비스무리한 수열
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보
www.acmicpc.net
반응형
'백준' 카테고리의 다른 글
| [백준 BOJ 1654번] 랜선 자르기 (C / C++ ) [이분 탐색, 이진 탐색] (0) | 2021.03.15 |
|---|---|
| [백준 BOJ 1753번] 최단경로 (C / C++ ) [다익스트라] (0) | 2021.03.13 |
| [백준 BOJ 15624번] 피보나치 수 7 (C / C++ ) [DP, 다이나믹 프로그래밍] (0) | 2021.03.10 |
| [백준 BOJ 2775번] 부녀회장이 될테야 (C / C++ ) [수학] (0) | 2021.03.10 |
| [백준 BOJ 2309번] 일곱 난쟁이 (C / C++ ) [브루트포스 알고리즘] (0) | 2021.03.10 |