[백준 9625번] BABBA (C++)

문제링크 : https://www.acmicpc.net/problem/9625

 

#include <bits/stdc++.h> 
using namespace std;

int n;
int dpA[46];
int dpB[46];

int main()
{
	dpA[0] = 0, dpA[1] = 1;
	dpB[0] = 1; dpB[1] = 1;
	cin >> n;
	for (int i = 2; i < n; i++)
	{
		dpA[i] = dpA[i - 1] + dpA[i - 2];   //규칙을 살펴보면 피보나치 수열을 따름
		dpB[i] = dpB[i - 1] + dpB[i - 2];
	}
	cout << dpA[n - 1] << ' ' <<dpB[n - 1];
}

일단 경우의 수를 나열해보면 규칙이 피보나치 수열을 따른 다는 것을 알 수 있다.