백준 9625번 : BABBA (C 언어)

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

9625번: BABBA

Code:

#include <stdio.h>
 
int main() {
    //0 1 1 2 3 5
    //1 0 1 1 2 3 
    int dpA[10001] = { 0, };
    int dpB[10001] = { 0, };
    dpA[0] = 1;
    dpB[0] = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        dpA[i] = dpB[i - 1];
        dpB[i] = dpB[i - 1] + dpA[i - 1];
    }
    printf("%d %d", dpA[n], dpB[n]);
    return 0;
}

문제풀이:

1. 문제 설명

상근이가 발견한 신기한 기계는 화면에 표시된 'A'를 'B'로, 'B'를 'BA'로 변환하는 기능을 가지고 있습니다. 이 변환은 기계의 버튼을 누를 때마다 실행됩니다. 우리의 목표는 버튼을 K번 눌렀을 때 화면에 표시되는 'A'와 'B'의 개수를 찾는 것입니다.

2. 코드 설명

이 문제를 해결하기 위해 동적 프로그래밍을 사용했습니다. 각 문자의 개수는 이전 단계의 문자 개수에 의존하므로, 이전 단계의 결과를 저장하면서 답을 찾아갑니다.

1. 먼저 'A'와 'B'의 개수를 저장할 두 개의 배열 dpA와 dpB를 초기화합니다. 초기 상태에서는 'A'가 하나 있고 'B'는 없으므로, dpA[0]는 1로, dpB[0]은 0으로 설정합니다.
2. 그리고 사용자로부터 정수 n을 입력 받습니다. 이 n은 버튼을 누를 횟수입니다.
3. 그 후 for문을 이용하여 1부터 n까지 반복합니다:

• dpA[i]는 이전 dpB 값, 즉 dpB[i-1]를 저장합니다. 이는 기계가 'B'를 'BA'로 변환하므로, 이전 단계에서 'B'의 개수가 현재 단계에서 'A'의 개수가 됩니다.
• dpB[i]는 이전 dpB 값과 이전 dpA 값을 더한 것을 저장합니다. 이는 기계가 'A'를 'B'로, 'B'를 'BA'로 변환하므로, 이전 단계에서 'A'와 'B'의 개수가 합쳐져 현재 단계에서 'B'의 개수가 됩니다.

1. 마지막으로, dpA[n]과 dpB[n]을 출력합니다. 이 값들은 각각 버튼을 n번 누른 후 'A'와 'B'의 개수를 나타냅니다.