[SWEA] 3316. 동아리실 관리하기

단순한 경우의 수 계산 문제인줄 알고 수학적으로 접근했다가 엄청 헤멨다.

 

처음에는 현재 관리자를 포함해 나올 수 있는 경우의 수를 다 센 다음에 열쇠를 건네받을 수 없는 경우만 따로 빼는 식으로 계산했는데, 이게 내가 생각한 것보다 따져야할 경우의 수가 너무 많아서 숫자가 자꾸 틀렸다.

 

결국 검색을 해봤는데 비트마스킹으로 일일이 경우의 수를 계산하는 문제였음...

(참고한 코드는 여기 : willbfine.tistory.com/330)

 

A, B, C, D가 i번째 날에 나오는 경우의 수는 총 2^4 - 1 = 15가지이고, 최대 날 수는 10000이므로

dp[10000][16] 크기의 배열을 생성해서 각 날마다의 경우의 수를 일일이 계산해주고,

총 경우의 수는 dp[10000][1]부터 dp[10000][15]까지 더해주면 된다.

 

숫자가 많이 크기 때문에 코드 잘못 짜면 stack overflow나니까 조심하자...

 

*** 주의할 점 및 실수했던 점 ***

• 첫째 날에는 무조건 A가 열쇠를 가지고 있다.
• 처음에 dp 배열을 테스트케이스마다 선언해줘서 stack overflow가 발생했다. dp는 전역변수로 선언해주고 매 테스트케이스마다 초기화해주자.
• 경우의 수가 추가될 때마다(계산될 때마다) %1000000007 안해주면 숫자가 또 다르게 나오니 주의...ㅠ (처음에 dp 일일이 다 계산하고 맨 마지막에만 modulo 계산했는데 틀렸었음..ㅠ) 

// SWEA_3316_동아리실_관리하기.cpp
using namespace std;
#include <iostream>
#include <string>
#include <cstring>
#define MAX 10000

long long dp[MAX][16]; // A, B, C, D 경우의 수 2^4 - 1 = 15

int main()
{
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		string club;
		cin >> club;
		
		long long case_cnt = 0;
		memset(dp, 0, sizeof(dp));

		for (int day = 0; day < club.size(); day++) {
			int admin = 1 << (club[day] - 'A');
			
			for (int i = 1; i < 16; i++) {
				if (day == 0) { // 1일차
					// i번째 경우에 관리자와 A가 포함되면
					if ((i & admin) != 0 && (i & 1) != 0) {
						dp[day][i] = 1;
					}
				}
				else { // 2일차 ~
					// 전날까지의 경우의 수가 0이 아니면
					if (dp[day - 1][i] != 0) {
						for (int j = 1; j < 16; j++) {
							// 전날 나온 사람이 오늘도 나오고 (i & j != 0)
							// 오늘 나온 사람이 관리자인 경우 count (j & admin != 0)
							if ((i & j) != 0 && (j & admin) != 0) {
								dp[day][j] += dp[day - 1][i];
								dp[day][j] %= 1000000007;
							}
						}
					}
				}
			}
		}
		for (int i = 1; i < 16; i++) {
			case_cnt += dp[club.size() - 1][i];
			case_cnt %= 1000000007;
		}
		printf("#%d %llu\n", tc, case_cnt);
	}
}