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

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

문제

---

ABCD 인원을 각각 1111 로 표현해 비트 연산으로 그날 활동 유무를 알 수 있다. 또한 dp를 사용해 f(d, currentState) = sum(f(d - 1, previousState)) 를 만족하면서 교집합이 존재해야하고 당일 책임자가 필수로 구할 수 있다.

실수

---

코드

---

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();

        int currentDayState, daySum, result;
        String line;
        sc.nextLine();
        for (int test_case = 1; test_case <= T; test_case++) {

            /////////////////////////////////////////////////////////////////////////////////////////////
            line = sc.nextLine();
            int[][] stateSet = new int[line.length() + 1][16];
            stateSet[0][1] = 1;

            for (int i = 1; i <= line.length(); i++) {
                currentDayState = 0;

                // 당일 담당자 추가
                switch (line.charAt(i - 1)) {
                    case 'A':
                        currentDayState = currentDayState | 0B0001;
                        break;
                    case 'B':
                        currentDayState = currentDayState | 0B0010;
                        break;
                    case 'C':
                        currentDayState = currentDayState | 0B0100;
                        break;
                    case 'D':
                        currentDayState = currentDayState | 0B1000;
                        break;

                }

                // 전날과 교집합 검사 후 추가.
                for (int j = 1; j < 16; j++) {
                    daySum = 0;
                    for (int j2 = 1; j2 < 16; j2++) {
                        if ((currentDayState == (j & currentDayState)) && ((j & j2) != 0B0000)) {
                            daySum = (daySum + stateSet[i - 1][j2]) % 1000000007;
                        }
                    }
                    stateSet[i][j] = daySum;
                }
            }

            result = 0;
            for (int i = 0; i < 16; i++) {
                result = (result + stateSet[line.length()][i]) % 1000000007;
            }
            System.out.println("#" + test_case + " " + result);
        }
	}
}