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

문제

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

해결방법

간단한 DP 문제이다.

dp 배열을 [버튼 누른 횟수][A or B] 형식으로 사용할 것이기에 dp[46][2]로 선언해준다.

dp[i][0]은 버튼을 i번 눌렀을 때 A의 개수, dp[i][1]은 B의 개수이다.

 

버튼을 누른 후 B는 BA로, A는 B로 바뀌므로 A와 B의 개수를 구하는 식은 다음과 같다.

A의 개수 = 버튼을 누르기 전 B의 개수

B의 개수 = 버튼을 누르기 전 A의 개수 + B의 개수

 

따라서 식으로 정리해보자면,

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

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

 

코드

#include <iostream>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int dp[46][2] = { 0, };
	int k;
	cin >> k;

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

	for (int i = 1; i <= k; i++) {
		dp[i][0] = dp[i-1][1];
		dp[i][1] = dp[i-1][0] + dp[i-1][1];
	}

	cout << dp[k][0] << ' ' << dp[k][1];

	return 0;
}