알고리즘 문제풀이/DP
[DP] 백준-BABBA C++ 9625번
taene_
2023. 9. 21. 13:20
https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
#include <iostream>
using namespace std;
int main()
{
int dpA[46] = { 0,0,1,1, };
int dpB[46] = { 0,1,1,2, };
for (int i = 4; i <= 45; i++)
{
dpA[i] = dpA[i - 2] + dpA[i - 1];
dpB[i] = dpB[i - 2] + dpB[i - 1];
}
int k;
cin >> k;
cout << dpA[k] << ' ' << dpB[k];
return 0;
}규칙: index = i 의 A와 B의 개수가 (i-2)의 개수+(i-1)의 개수이다.