BABBA #9625 c++ 풀이

https://www.acmicpc.net/problem/9625

9625번: BABBA

차분히 먼저 적어보았다. dp문제는 규칙을 찾는게 중요하다.

iter수 -> 모양 A개수 B개수를 써봤다.

0-> A 1 0 

1-> B 0 1

2-> BA 1 1 

3-> BAB 1 2 

4-> BABBA 2 3

여기서 점화식이 보였다.

5-> BABBABAB 3 5 

6-> BABBABABBABBA 5 8

그결과 

dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
dp[i][0] = dp[i - 1][1];

 

라고 알 수 있게 되었다. 정답은 다음과 같다.

#include<iostream>

using namespace std;
int k;
int dp[46][2]; // 0열은 A의 수, 1열은 B의 수

int main() {
	cin >> k; 

	dp[0][0] = 1;
	dp[0][1] = 0;

	dp[1][0] = 0;
	dp[1][1] = 1;

	for (int i = 2; i <= k; i++) {
		dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][0] = dp[i - 1][1];
	}
	cout << dp[k][0] << " " << dp[k][1];
	//for(int )
	return 0;
}