Codetesing의 코딩공부

비트마스크를 활용한 DP문제다.

아까 풀어봤기 때문에 어려움없이 쉽게 풀 수 있었다.

다만 여기선 무조건 있어야 되기 때문에 and 연산자를 사용했다.

#define MOD 1000000007

#include<iostream>
#include<string>
#include<cstring>

using namespace std;

long long DP[10001][16];

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		string in; cin >> in;
		int len = in.length();
		memset(DP, 0, sizeof(DP));

		for (int i = 0; i < len; i++)
		{
			int admin = 1 << (in[i] - 'A');

			for (int j = 1; j < 16; j++)
			{
				if (i == 0)
				{
					if ((j & admin) != 0 && (j & 1) != 0)
					{
						DP[i][j] = 1;
					}
				}
				else
					if (DP[i - 1][j] != 0)
						for (int k = 1; k < 16; k++)
							if ((k & j) != 0 && (k & admin) != 0)
							{
								DP[i][k] += DP[i - 1][j];
								DP[i][k] %= MOD;
							}
			}
		}

		long long out = 0;
		for (int i = 1; i < 16; i++)
		{
			out += DP[len - 1][i];
			out %= MOD;
		}

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

비트마스크를 사용하여 DP를 활용한 문제이다.

비트마스크 관련 문제는 처음 풀어보았기 때문에 비트마스크에 대해 공부하고 풀었다.

동적프로그래밍/비트마스크/계단수 : 백준 10844번, 1562번 (tistory.com)​

비트마스크는 2진법을 활용해 부분집합을 표현하는 방식인것 같다.

 i는 자릿수며 초기설정 i == 1 일때 모두 삐끗수이기 때문에 1로 설정한다.

다음 숫자에서 0 - 9까지 들어갈 수 있는지 확인 하기위해 j = 0 - 9, k = 0 - 1023 반복하는데 (1 << j) | k를 사용해 상태를 확인한다.

이 문제에서는 0 - 9까지이고 0 - 9까지 모두 사용해야 하기 때문에, DP[n][][1023]의 합을 답으로 한다.

#define MOD 1000000000

#include<iostream>

using namespace std;

int DP[101][10][1 << 10];

void BIT_MASK()
{
	for (int i = 1; i < 10; i++)
		DP[1][i][1 << i] = 1;

	for(int i = 0; i < 100; i++)
		for(int j = 0; j < 10; j++)
			for (int k = 0; k < 1024; k++)
			{
				if(j != 0)
					DP[i + 1][j][(1 << j) | k] = (DP[i + 1][j][(1 << j) | k] + DP[i][j - 1][k]) % MOD;
				if(j != 9)
					DP[i + 1][j][(1 << j) | k] = (DP[i + 1][j][(1 << j) | k] + DP[i][j + 1][k]) % MOD;
			}
}

int STAIR_NUM(int n)
{
	int sum = 0;

	for (int i = 0; i < 10; i++)
	{
		sum += DP[n][i][1023];
		sum %= MOD;
	}

	return sum;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	BIT_MASK();

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N; cin >> N;
		int out;

		if (N < 10)
			out = 0;
		else
			out = STAIR_NUM(N);

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}