[백준] 9625_BABBA

[문제]: 9625번: BABBA (acmicpc.net)

 

A와 B의 개수를 세기 위해 pair타입을 이용했다. pair<int, int> 타입은 (A의 개수, B의 개수) 형식이다. 문자열을 본다면 스위치를 k번 눌렀을 때 문자열은 항상 (k-1번 문자열 + k-2번 문자열)이다. 식으로 표현하면,

\[strPush(k) = strPush(k-1)+strPush(k-2)\]

(예)

스위치를 5번 누른 문자열 = "BABBABAB"

스위치를 4번 누른 문자열 = "BABBA"

스위치를 3번 누른 문자열 = "BAB"

 

여기서 오해하지 말아야 할 것은 + 연산이 실제로 더하기를 의미하는 것은 아니고 문자열의 concatenate, 즉 문자열을 연결하는 연산이다. 실제 문제는 문자열이 아닌 A와 B의 개수를 구하는 것이기 때문에 위 식을 토대로 구현하되 A와 B의 개수를 재귀적으로 카운팅 하여 계산했다. 반복 계산을 피하기 위해서 메모제이션 기법을 사용한 부분도 참고할 것. 

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

using p = pair<int, int>;

vector<p> DP(46, make_pair(-1, -1));

p SumPair(const p& a, const p& b)
{
	return { a.first + b.first, a.second + b.second };
}

p Push(int k)
{
	if (k == 0) return make_pair(1, 0);
	if (k == 1) return make_pair(0, 1);
	if (DP[k] != make_pair(-1, -1))
		return DP[k];
	return DP[k] = SumPair(Push(k - 1), Push(k - 2));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int K;
	cin >> K;
	p ret = Push(K);
	cout << ret.first << " " << ret.second << '\n';
	return 0;
}

 

사실.. 이렇게 풀 필요가 없다. 이렇게 어렵게 풀 필요 없이 문제에서 주어진 규칙인 B는 BA로, A는 B로 바뀐다는 것을 기억하면 끝이다. B는 다음 스위치에 항상 1개의 B와 1개의 A가 추가되고, A는 다음 스위치에서 항상 1개의 B가 추가된다.