[비트 DP] (CHECK) SWEA 3316 동아리실 관리하기 C++

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBnFuhqxE8DFAWr 

SW Expert Academy

#include <iostream>
#include <cstring> // memset

using namespace std;

int dp[10000][16];  // 자료형 조심, 16가지 조합 모두 계산

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

	for (test_case = 1; test_case <= T; ++test_case) {
		string str;
		cin >> str;
		memset(dp, 0, sizeof(dp));

		for (int i = 0; i < str.size(); i++) {
			int temp = 1 << (str[i] - 'A');

			for (int j = 1; j < 16; j++) {
				if (i == 0) {
					// temp 관리자 있고, A 있는 조합의 경우
					if (((temp & j) != 0) && ((j & 1) != 0)) dp[i][j] = 1;
				}
				else {
					for (int k = 1; k < 16; k++) { // j, k 위치 바뀌어도 가능
						// temp 관리자 있고, 이전 날에 있었던 사람이 다음 날에도 있는 경우
						if (((temp & j) != 0) && ((j & k) != 0)) {
							dp[i][j] += dp[i - 1][k];
							dp[i][j] %= 1000000007;
						}
					}
				}
			}
		}

		int ans = 0;
		for (int i = 1; i < 16; i++) {
			ans += dp[str.size() - 1][i];
			ans %= 1000000007;
		}

		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;
}