[백준,c++] 9625번 - BABBA

문제

9625번: BABBA

 

코드

#include <iostream>
using namespace std;

int A[46],B[46];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n; cin>>n;
    
    A[0]=1; B[0]=0;
    A[1]=0; B[1]=1;
    A[2]=1; B[2]=1;
 
    
    for(int i=3; i<=n; i++){
        A[i] = B[i-1];
        B[i] = A[i-1] + B[i-1];
    }
    cout<<A[n]<< ' '<<B[n];
}

 

풀이

간단한 DP문제였습니다.

A[0] =1, B[0] = 0 (제일 초기 상태)

A[1]=0, B[1] = 1 (한번 눌렀을 때)

A[2]=1, B[2] = 1 (두 번 눌렀을 때) 

이렇게 초기값을 설정해주고 살펴보면 A[n] = B[n-1], B[n] = A[n-1] + B[n-1] 의 점화식을 도출해낼 수 있습니다.