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

19 Jul 2022 in Study on Algorithm, SAMSUNG DX, SWEA

SW Expert Academy
3316. 동아리실 관리하기

• 코드
• 잡담

---

---

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[10000][16]; // 날짜당 경우의 수 dp

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

	int tc;
	cin >> tc;

	for (int t = 1; t <= tc; t++) {
		
		string s;
		cin >> s;

		int n = s.size();
		ll cnt = 0;

		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; i++) {

			int manager = (1 << (s[i] - 'A'));

			for (int j = 1; j < 16; j++) {
				if (i == 0) {
					// A가 포함될 때, 책임자가 포함될 때
					if ((j & 1) != 0 && (j & manager) != 0) {
						dp[i][j] = 1;
					}
				}
				else {
					for (int k = 1; k < 16; k++) {
						// 전날과 겹치는 인원이 있을 때, 책임자가 포함될 때
						if ((j & k) != 0 && (k & manager) != 0) {
							dp[i][k] += dp[i - 1][j];
							dp[i][k] %= 1000000007;
						}
					}
				}
			}
		}

		for (int j = 1; j < 16; j++) {
			cnt += dp[n - 1][j];
			cnt %= 1000000007;
		}

		cout << "#" << t << " " << cnt << "\n";
	}
	return 0;
}

잡담

어떻게 푸는지 모르겠어서 검색 찬스를 썼다.
참고한 글은 여기
역시 비트 연산에는 아직 취약한가 보다.
정답 코드를 보고도 이해하는데에 좀 걸렸다…

핵심은 다음과 같다.

1. 날마다의 책임자 변수 manager
2. 첫 날의 열쇠 소유자는 A
3. 열쇠는 인수인계 되어야 하므로 전날과 당일에는 동일한 인원이 항상 있어야함

그리고 문제에서 너무 커지는 답을 방지하기 위해 1000000007로 나눈 값을 요구하는데, 이런 문제의 경우 dp의 어느 시점에서든 1000000007으로 나누어 주어도 괜찮다는 점을 유의해 overflow를 방지하자.