[9625] BABBA

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

9625번: BABBA

<문제>

바뀌기 전의 알파벳은 A와 B, 모두 한글자 이므로

"AABBA", "ABABA", "BBAAA"처럼 각 알파벳의 개수는 동일하다면, 순서가 바뀌어도 결과는 변하지 않는다.

결국 현재 상태에 영향을 미치는건 버튼을 누른 횟수 N,

이후의 상태를 알기위해 현재에 저장해두어야 하는것은 'A'와 'B'의 개수가 되겠다.

 

이를 2차원 dp[N][2]로 선언해주어 아래처럼 dp를 채워나가고, dp[N][0]과 dp[N][1]을 출력하면 된다.

dp[i][0] : i번 버튼을 눌렀을때의 'A'의 개수
dp[i][1] : i번 버튼을 눌렀을때의 'B'의 개수

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int dp[50][2], n;
int main(void) {
    int i;
    cin >> n;
    dp[0][0] = 1;
    dp[0][1] = 0;
    for (i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
    }
    cout << dp[n][0] << " " << dp[n][1];
    return 0;
}