[C++] 백준 17520번 Balanced String

DP로 문제를 해결했습니다.

균형잡힌 문자열을 찾는 문제로 0과 1의 개수차이가 1개 이하인 경우의 수를 구하는 문제입니다.

2로 나누어떨어지면 값을 그대로 가져오며,
나누어 떨어지지 않는 경우 이전 값의 2배를 증가시켰습니다.

 

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

typedef long long ll;

int main(int argc, char* argv[])
{
	int n;
	ll DP[100010];

	cin >> n;

	DP[1] = 2;

	for (int i = 2; i <= n; ++i) {
		if (i % 2 == 0) {
			DP[i] = DP[i - 1];
		}
		else {
			DP[i] = (DP[i - 1] * 2) % 16769023;
		}
	}

	cout << DP[n] << endl;

	return 0;
}