[BOJ 16650 // C++] Counting Stairs

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16650번 문제인 Counting Stairs이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/16650 

16650번: Counting Stairs

문제에서 찾아야하는 계단 모양들은 맨 왼쪽 아래 칸을 포함하는 가장 큰 정사각형 S와 윗 부분 A, 오른쪽 부분 B의 세 부분으로 분리하여 생각할 수 있다.

 

주어지는 블럭의 개수 N에서 S를 구성하는 블럭의 개수를 뺀 개수가 홀수라면 A와 B를 개수가 같게 구성할 수 없으므로, N이 홀수이면 S의 변의 길이는 홀수, N이 짝수이면 S의 변의 길이는 짝수가 되어야 한다.

 

A 하나를 구성하는 블럭의 개수를 X, S의 변의 길이를 K라 하자. 이 때, A를 구성하는 방법은 "X를 K개의 (0 이상의 정수)로 분할하는 경우의 수", 즉 "X+K를 K개의 (1 이상의 정수)로 분할하는 경우의 수"와 같다.

 

n을 k개의 1 이상의 정수로 분할하는 경우의 수를 P(n,k)라 할 때, P(n,k) = P(n-k,k) + P(n-1,k-1) 과 같은 점화관계가 성립한다는 사실은 잘 알려져있다. (초기값은 P(0,0) = 1, 그 외 n<1 또는 k<1인 경우 P(n,k) = 0이다.) 메모이제이션을 잘 하여 위의 식을 이용해 문제를 해결하자.

 

이 문제에서 K는 sqrt(N)을 넘을 수 없으므로, 최악의 경우 직접 조사하게 되는 P(n,k)의 값의 가짓수는 약 Nsqrt(N)가지가 된다. 이는 문제 해결에 충분한 가짓수이다.

 

아래는 제출한 소스코드이다.

#define MOD 998244353
#include <iostream>
#include <vector>
using namespace std;

int dp[200001][448];

int partition(int N, int K) {
	if (N < K) return 0;
	if (N <= 0 || K <= 0) {
		if (N == 0 && K == 0) return 1;
		return 0;
	}

	int& dpNK = dp[N][K];
	if (dpNK) return dpNK;
	dpNK = partition(N - K, K) + partition(N - 1, K - 1);
	if (dpNK >= MOD) dpNK -= MOD;
	return dpNK;
}

void solve() {
	int N; cin >> N;
	int ans = 0;
	if (N & 1) {
		for (int i = 1; i * i <= N; i += 2) {
			int tmp = (N - i * i) >> 1;
			ans += partition(tmp + i, i);
			if (ans >= MOD) ans -= MOD;
		}
	}
	else {
		for (int i = 2; i * i <= N; i += 2) {
			int tmp = (N - i * i) >> 1;
			ans += partition(tmp + i, i);
			if (ans >= MOD) ans -= MOD;
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}