[Baekjoon] BABBA

👀 문제 설명

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

 

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

 

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

 

예제 입력 1

1

 

예제 출력 1

0 1

 

✍🏻풀이

DP를 사용하는 문제이다.

처음에는 dp를 string 배열로 생성하고 문제를 풀었으나 메모리 초과가 났다.

dp[0] = "A", dp[1] = "B", dp[2] = "BA", dp[3] = "BAB", dp[4] = "BABBA" ... 의 식을 갖고 있는데 즉, dp[i] = dp[i- 1] + dp[i - 2]이다.

 

string 배열이 아닌, int형 배열을 사용해서 문제를 풀면 메모리 초과가 나지 않는다.

dpA는 i번째 눌렀을 때, 화면에 A가 몇 개 뜨는지 저장하는 배열이고, dbB는 B가 몇개인지 저장하는 배열이다.

마찬가지로 위의 식과 동일하다.

 

메모리 초과가 string 때문인 것 같긴한데.. 확실하지 않다..

 

코드

string 배열 사용 코드(메모리 초과)

 

#include <stdio.h>
#include <iostream>

using namespace std;

string dp[46];

int main() {
    int K;
    cin >> K;

    dp[0] = "A"; dp[1] = "B";
    for (int i = 2; i <= K; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    int a = 0, b = 0;
    for (int index = 0; index < dp[K].length(); index++) {
        if (dp[K][index] == 'A')
            a++;
        else
            b++;
    }

    cout << a << " " << b;
}

 

int 배열 사용(정답)

#include <stdio.h>
#include <iostream>

using namespace std;

int dpA[46];
int dpB[46];

int main() {
    int K;
    cin >> K;

    dpA[0] = 1; dpA[1] = 0;
    dpB[0] = 0; dpB[1] = 1;
    
    for (int i = 2; i <= K; i++) {
        dpA[i] = dpA[i - 1] + dpA[i - 2];
        dpB[i] = dpB[i - 1] + dpB[i - 2];
    }
    
    cout << dpA[K] << " " << dpB[K];
}