백준 9625번: BABBA (C++)

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

9625번: BABBA

---

Solved By: DP

 

A는 직전의 문자열에서 B들이 변환된 것이라 볼 수 있습니다.

B는 "BA"로 전환되기 때문에 직전 문자열에서 B의 개수와 A에서 변환되는 B의 개수를 모두 합하여 각각 A, B의 개수를 알 수 있습니다.

 

#include <iostream>
#define MAX 46
using namespace std;

int A[MAX], B[MAX];

int main(){
    int k; cin >> k;
    A[0] = 1;
    
    for(int i = 1; i <= k; i++){
        A[i] = B[i - 1];
        B[i] = B[i - 1] + A[i - 1];
    }
    
    cout << A[k] << ' ' << B[k];
    return 0;
}