[백준/BOJ] 백준 17520번 : Balanced String

www.acmicpc.net/problem/17520

17520번: Balanced String

이진 문자열이 아무것도 없는 상태부터 시작하여 0의 개수와 1의 개수가 같을 때, 0의 개수가 더 많을때, 1의 개수가 더 많을때를 고려하여 상황에 맞게 균형 잡힌 문자열을 만드는 숫자를 넣어가며 총개수를 센다, 0의 개수와 1의 개수가 같을때는 0과 1 모두 추가할 수 있는데, 이때 0을 추가했을 때와, 1을 추가했을 때 각각 상황의 개수는 같으므로 0을 하나 더 추가했다고 하고, 그것의 2배를 하여 1이 추가 됐을 때도 고려한다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;

int Solve(int num0, int num1)
{
	//모든 개수를 다 세었을때
	if (num0 + num1 == n)
		return 1;

	int ret = 0;

	//0의 개수와 1의 개수가 같을때
	if (num0 == num1)
	{
		ret += (Solve(num0 + 1, num1) + 16769023) % 16769023; //0을 하나 더 넣음
		ret = (ret * 2 + 16769023) % 16769023; //1을 더 넣은것도 고려하여 2배를 함(0을 하나 더 넣은것과 1을 하나 더 넣은것의 개수는 같다)
	}

	//0의 개수가 더 클때
	else if (num0 > num1)
	{
		//1을 더 넣음
		ret += (Solve(num0, num1 + 1) + 16769023) % 16769023;
	}

	//1의 개수가 더 클때
	else if (num0 < num1)
	{
		//0을 더 넣음
		ret += (Solve(num0 + 1, num1) + 16769023) % 16769023;
	}

	ret %= 16769023;

	return ret;
}

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

	cin >> n;

	cout << Solve(0, 0);

	return 0;
}