반응형
https://www.acmicpc.net/problem/2747
2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된��
www.acmicpc.net
간단한 재귀함수 또는 for문으로 작성할 수 있는 dp문제입니다.
Code :
1. for문 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream> using namespace std; int main(){ int num; cin >> num; //방 개수 int *arr = new int [num+1]; arr[0] = 0; arr[1] = 1; if(num == 0 || num == 1){ cout<<num; return 0; } for(int i = 2; i <= num; i++){ arr[i] = arr[i-2]+arr[i-1]; } cout<<arr[num]; } | cs |
2. dp :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <iostream> #define ll long long using namespace std; ll f[45]; ll fibo(int n){ ll &ret = f[n]; if(n==0) return ret = 0; if(n<=2) return ret = 1; if(ret) return ret; return ret = fibo(n-1) + fibo(n-2); } int main(){ int n; cin >> n; cout << fibo(n) << '\n'; } | cs |
'Algorithm' 카테고리의 다른 글
| 백준(baekjoon)(BaekJoon)코딩 1978번:소수찾기 답 (0) | 2016.09.23 |
|---|---|
| 백준(baekjoon)(BaekJoon)코딩 2581번:소수 답 (0) | 2016.09.23 |
| (C++) - 백준(BOJ) 8958번 : OX퀴즈 답 (0) | 2016.09.23 |
| 백준(baekjoon)(BaekJoon)코딩 1929번:에라토스테네스의 체 답 (0) | 2016.09.23 |
| 백준(baekjoon)(BaekJoon)코딩 2751번:힙 정렬(Heap Sort) 답 (0) | 2016.09.23 |