다이나믹 프로그래밍 문제입니다.
위의 피보나치 함수를 실행할때 fibonacci(0)과 fibonacci(1)이 각각 몇번 실행되는지 구하는 문제입니다.
0이면 0을 리턴해주므로
0 = (1 0)
1이면 1을 리턴해주므로
1 = (0 1)
2면 2-1, 2-2를 실행시키므로
2 = (1 0) + (0 1)
2 = (1 1)이 됩니다.
3도 마찬가지로 3-1, 3-2를 실행시키는 방식으로 구할 수 있습니다.
memo[50][2]를 선언하였고 앞배열은 숫자 뒤에 배열은 0과 1의 개수를 넣었습니다.
memo[i][0] = memo[i-1][0] + memo[i-2][0]; // 0의 개수를 구함
memo[i][1] = memo[i-1][1] + memo[i-2][1]; // 1의 개수를 구함
위의 코드를 찾는 숫자까지 반복하여서 문제를 해결하였습니다.
#include <iostream>
using namespace std;
int memo[50][2];
void init()
{
for (int i = 0; i < 50; ++i) {
for (int j = 0; j < 50; ++j) {
memo[i][j] = -1;
}
}
memo[0][0] = 1;
memo[0][1] = 0;
memo[1][0] = 0;
memo[1][1] = 1;
}
int main(int argc, char *argv[])
{
init();
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
if (memo[num][0] != -1) {
cout << memo[num][0] << " ";
cout << memo[num][1] << endl;
continue;
}
for (int j = 2; j <= num; ++j) {
if (memo[j][0] != -1) {
continue;
}
memo[j][0] = memo[j - 1][0] + memo[j - 2][0];
memo[j][1] = memo[j - 1][1] + memo[j - 2][1];
}
cout << memo[num][0] << " ";
cout << memo[num][1] << " " << endl;
}
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 1912번 연속합 (0) | 2019.05.17 |
---|---|
[C++] 백준 2156번 포도주 시식 (0) | 2019.05.17 |
[C++] 백준 1932번 정수 삼각형 (0) | 2019.05.17 |
[C++] 백준 2193번 이친수 (0) | 2019.05.17 |
[C++] 백준 1149번 RGB거리 (0) | 2019.05.09 |