1562번: 계단 수 - DP(비트마스킹)

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

1562번: 계단 수

 

dp[i][j][k] : 길이가 i이고 끝 숫자가 j이며 등장한 숫자들을 나타내는 수가 k(비트마스킹 이용)일 때의 경우의 수

dp[i][j][k] = dp[i - 1][j - 1][k ^ (1 << j)] + dp[i - 1][j + 1][k ^ (1 << j)] + dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k]

즉, 길이가 1 작고, 끝 숫자 j와 1 차이나며, j가 k에 있거나 없는 경우의 수들의 합

단, j = 0, 9일 때는 예외 처리를 해 주어야 한다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#define mod 1000000000
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N;
ll dp[101][10][1024]; //길이, 끝 숫자, 등장한 숫자들

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

	cin >> N;
	for (int i{ 1 }; i <= 9; i++)
	{
		dp[1][i][1 << i] = 1;
	} //길이 1일 때

	for (int i{ 2 }; i <= N; i++)
	{
		for (int j{ 0 }; j <= 9; j++)
		{
			for (int k{ 0 }; k < 1024; k++)
			{
				if (k & (1 << j)) //끝 숫자 j가 등장한 숫자들에 포함
				{
					if (j == 0)
					{
						dp[i][j][k] = (dp[i - 1][j + 1][k ^ (1 << j)]
							+ dp[i - 1][j + 1][k]) % mod;
					}
					else if (j == 9)
					{
						dp[i][j][k] =
							(dp[i - 1][j - 1][k ^ (1 << j)]
							+ dp[i - 1][j - 1][k]) % mod;
					}
					else
					{
						dp[i][j][k] =
							(dp[i - 1][j - 1][k ^ (1 << j)] + dp[i - 1][j + 1][k ^ (1 << j)]
							+ dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k]) % mod;
					}
				}
			}
		}
	}

	ll ans{ 0 };
	for (int i{ 0 }; i <= 9; i++)
	{
			ans += dp[N][i][1023];
			ans %= mod;
	}
	cout << ans;
}