[C++] 백준 9625번 BABBA

버튼을 누를때마다 다음 처럼 변경됩니다.
A -> B
B -> BA
이 때 n번 버튼을 누르면 A와 B의 개수를 구하는 문제입니다.

        A B
1번 = 0 1
2번 = 1 1
3번 = 1 2
4번 = 2 3
5번 = 3 5

1번~5번을 보면은 
A와 B는 각각 피보나치 형태를 가지는것을 확인할 수 있습니다.
DP배열을 만들어서 피보나치를 계산하고 결과값을 출력해주었습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(int argc, char * argv[])
{
	int n;
	int DP[50][2];

	cin >> n;

	DP[0][0] = 0;
	DP[0][1] = 0;
	DP[1][0] = 0;
	DP[1][1] = 1;
	DP[2][0] = 1;
	DP[2][1] = 1;

	for (int i = 3; i <= n; ++i) {
		DP[i][0] = DP[i - 1][0] + DP[i - 2][0];
		DP[i][1] = DP[i - 1][1] + DP[i - 2][1];
	}

	cout << DP[n][0] << " " << DP[n][1] << endl;

	return 0;
}