시작

이 문제는 한번 잘 생각하면 쉬운 문제다. 그렇다면 왜 쉬운지 한번 알아보자. 우선 1일때 0 1을 출력하는 것을 알 수 있는데 이 이유는 A는 B로 바뀌고 B는 BA로 바뀌는데 처음엔 A하나밖에 없기때문에 0 1을 출력한다 그렇다면 2일땐 BA니 1 1, 3일땐 1 2, 4일땐 2 3 그렇다면 여기까지 봤을대 어느 수열과 비슷하다고 느낄 수 있다. 이 수열은 피보나치 수열과 유사하다 볼 수 있는데 이유는 피보나치 수열을 5번까지 한번 나열을 해보면 1 1 2 3 4, .... 이 되는 것을 알 수 있다 그렇다면 왜 유사하는지 보면 1일땐 0 1, 2일땐 1 1, 3일땐 1 2 즉 k - 2, k - 1번지의 수가 출력되는 것을 알 수 있다. 그러니 한번 피보나치를 이용하여 문제를 풀어보자

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>

const char AWORD = 'A';
const char BWORD = 'B';

using namespace std;

int fibo[101];

int k;

// 피보나치 수 시작
int Fibo(int i) {
	if (i == 0 || i == 1) return fibo[i] = 1;
	if (fibo[i] != 0) return fibo[i];
	return fibo[i] = Fibo(i - 1) + Fibo(i - 2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> k;

	// k가 1이면 B하나뿐
	if (k == 1) {
		cout << "0 1";
	}
	else {
		Fibo(k);
		cout << fibo[k - 2] << " " << fibo[k -1];
	}
}