PS/BOJ

백준 9625번: BABBA (C++)

도비(Doby) 2022. 5. 17. 23:12

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

 

9625번: BABBA

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했

www.acmicpc.net

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;
}