Boj 1562) 계단 수

문제

백준 1562

방법 1

설명

처음 풀었을 때 떠오른 방식으로 비트마스킹을 사용한 DP 이다.

점화식은 위 코드를 보면 쉽게 알 수 있다.

시간 복잡도

O(\(\mathrm{N} \times 1024 \times 10\))

코드

const int MOD = 1000000000;
int dp[2][1<<10][10];

// i => 맨 앞 숫자, j => 2번째 앞 숫자
void Apply(int i, int j, int mask)
{
	int& dst = dp[1][mask | (1 << i)][i];
	int& src = dp[0][mask][j];
	dst = (dst + src) % MOD;
}

int main()
{
	int n; cin >> n;

	for(int i = 0; i < 10; i++) dp[1][1 << i][i] = 1;
	for (int i = 2; i <= n; i++)
	{
		copy(dp[1][0], dp[2][0], dp[0][0]);
		fill(dp[1][0], dp[2][0], 0);
		for (int mask = 1; mask < (1 << 10); mask++)
		{	
			for (int j = 1; j < 9; j++)
			{
				Apply(j, j - 1, mask);
				Apply(j, j + 1, mask);
			}
			Apply(0, 1, mask);
			Apply(9, 8, mask);
		}
	}

	int ans = 0;
	for (int i = 1; i < 10; i++)
		ans = (ans + dp[1][0b1111111111][i]) % MOD;
	cout << ans;
}

방법 2

설명

일정 수 범위에 대해서 계단수를 구해서 포함배제의 원리를 이용해 푸는 방식이다. 이걸 어떻게 떠올리는지 놀라울 따름이다.

그런데 왜 하필 0~8 과 1~9 로 쪼개는걸까?

• I(n) = 숫자 1개로 이루어진 집합 + ... + 숫자 n개로 이루어진 집합 라고 하자. 우리가 구해야할 것은 숫자 10개로 이루어진 집합 으로 I(10) - I(9) 가 된다.
• I(10) = DP(0, 9) 는 자명하다
• 계단수의 특성으로 숫자가 하나가 부족한 경우는 0 또는 9 가 없는 경우 뿐이다. 그러므로 I(9) = DP(0, 8) + DP(1, 9) - DP(1, 8) 이다.
• 그러므로 DP(0, 9) - DP(0, 8) - DP(1, 9) + DP(1, 8) 가 정답이 된다.

DP(a, b) 는 쉬운 계단 수 를 푸는 방식에서 약간만 수정만 하면 된다. 이때 -1, 10 에 해당하는 공간을 따로 두어서 0, 9 에서 예외처리를 막으면 깔끔한 코드를 만들 수 있다.

시간 복잡도

O(\(\mathrm{N} \times 10\))

코드

const int MOD = 1000000000;
int dp[101][12], n;

int DP(int s, int e)
{
	s++; e++; // 0, 9 에서 예외를 막기위함
	fill(dp[0], dp[101], 0);

	for (int i = s; i <= e; i++) dp[1][i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = s; j <= e; j++)
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;

	int ans = 0;
	for (int i = max(s, 2); i <= e; i++)
		ans = (ans + dp[n][i]) % MOD;
	return ans;
}

int main()
{
	fastio;
	cin >> n;
	cout << (DP(0, 9) - DP(0, 8) - DP(1, 9) + DP(1, 8) + MOD) % MOD;
}