[백준] 알고리즘 9625번 - BABBA 문제

문제

www.acmicpc.net/problem/9625

9625번: BABBA

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[46];
int dp1[46];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int k;
	cin >> k;
	dp[0] = 1, dp[1] = 0;
	dp1[0] = 0, dp1[1] = 1;
	for (int i = 2; i <= k; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		dp1[i] = dp1[i - 1] + dp1[i - 2];
	}
	cout << dp[k] << " " << dp1[k];
}

풀이

예시에 나와있는 규칙대로 표를 만들어서 쭉 나열해보면 피보나치 수열을 이루고 있는 것을 확인할 수 있다.

간단하게 두 배열을 피보나치 구한 후 출력해준다.