[SWEA]3316. 동아리실 관리하기 D4 (java)

문제 풀이

비트마스크를 이용한 완전탐색 아닌 완전탐색, 빡구현 문제!
DFS를 이용한 풀이도 가능할 것 같다.
메모이제이션을 이용하여 부분 집합들에 대한 값을 관리해주었다.
상당히 for문이 많이 쓰였지만 10,000 * 16 * 16 이라 괜찮은... 듯 싶다.

첫 번째 for문은 전체 동아리실 관리 날짜 수 이다.
두 번째 for문은 동아리실 관리에 어제 참여한 사람들의 부분 집합을 구하기 위한 부분이다.
세 번째 for문은 동아리실 관리에 당일 참여한 사람들의 부분 집합을 구하기 위한 부분인데, 
어제를 먼저 확인하는 이유는 어제 참여하지 않은 사용자를 걸러내기 위함이다.
오늘 참여하는 사람(sub)이고, 당번(turn)이라면 값에 누적해서 연산해준다.

코드

 

import java.io.*;
 
class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T = Integer.parseInt(br.readLine());
        int R = 1_000_000_007;
        
        for (int test_case = 1; test_case <= T; test_case++) {
            String str = br.readLine();
            int N = str.length();
            long[][] record = new long[N][1 << 4];
 
            for (int day = 0; day < N; day++) {
                int turn = 1 << (str.charAt(day) - 'A');
 
                for (int sub = 0; sub < (1 << 4); sub++) { // 지난 날의 경우(어제)
                    if (day == 0) {
                        if ((sub & turn) > 0 && (sub & 1) > 0) {
                            record[0][sub] = 1;
                        }
                    } else {
                        if (record[day - 1][sub] == 0)
                            continue;
                        for (int i = 0; i < (1 << 4); i++) {// 다가올 날의 경우(오늘)
                            if ((sub & i) > 0 && (turn & i) > 0) {
                                record[day][i] += record[day - 1][sub];
                                record[day][i] %= R;
                            }
                        }
                    }
                }
            }
 
            long answer = 0;
            for (int i = 0; i < (1 << 4); i++) {
                answer += record[N - 1][i];
                answer %= R;
            }
            
            System.out.println("#" + test_case + " " + answer);
        }
    }
}