<백준> 9625

BABBA

문제
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.
기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.
버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력
첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력
첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

맨 처음에 규칙을 찾으려고 나열했었는데
B, BA, BAB, BABBA, BABBAB 이렇게 나열했었다.
근데 규칙도 안보이고 답이 계속 안나왔다.
근데 알고보니 B, BA, BAB, BABBA, BABBABA 이렇게 진행되는 것이었다. 두개의 다른 점은 나는 B 누르고 A 누르고 또 B누르고 이렇게 오로지 한 글자만 변환했었다.
하지만 B를 바꿔주고 두번째는 B도 바꾸고 A도 바꾸고 이렇게 한꺼번에 바꾸는 거였다.
처음엔 이해가 되지 않아 시간을 좀 썼는데 접근방식을 잘 찾아야할 것 같다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	int k;
	cin >> k;

	vector<int> dpA(1000);
	vector<int> dpB(1000);

	dpA[0] = 0;
	dpB[0] = 1;
	dpA[1] = 1;
	dpB[1] = 1;

	for (int i = 2; i < k; i++)
	{
		dpA[i] = dpA[i-1] + dpA[i -2];
		dpB[i] = dpB[i-1] + dpB[i-2];
	}

	cout << dpA[k - 1] << " " << dpB[k - 1];

}