문제
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int dp[41];
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int T;
cin >> T;
dp[0] = 1, dp[1] = 1, dp[2] = 1;
for (int i = 3; i <= 40; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
while (T--) {
int x;
cin >> x;
if (x == 0) cout << "1" << " " << "0"<<"\n";
else if (x == 1) cout << "0" << " " << "1"<<"\n";
else cout << dp[x-1] << " " << dp[x]<<"\n";
}
}해설
직접 5의 호출까지 해보게되면 규칙을 찾을 수 있다.
결국 0의 호출은 이전의 값과 같다는 것을 알 수 있고, 1의 호출은 피보나치를 구하는 것과 같다는 것을 알 수 있다.
1의 호출의 점화식 - dp[x] = dp[x-1] + dp[x-2]
'Algorithm > dynamic programming' 카테고리의 다른 글
| [백준] 알고리즘 C++ 10942번 - 팰린드롬?문제 (0) | 2022.01.24 |
|---|---|
| [백준] 알고리즘 C++ 1520번 - 내리막 길문제 (0) | 2022.01.24 |
| [백준] C++ 알고리즘 2294번 - 동전2문제 (0) | 2021.09.10 |
| [백준] 알고리즘 11048번 - 이동하기문제 (0) | 2021.09.08 |
| [백준] 알고리즘 11060번 - 점프 점프 문제 (0) | 2021.04.28 |
