[SWEA] 3316 동아리실 관리하기 D4 / JAVA

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

SW Expert Academy

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 길이 10,000 이하인 하나의 문자열이 주어진다. 이 문자열은 A, B, C, D로 이루어져 있으며, i번째 문자는 i번째 날의 책임자가 누구인지를 나타낸다.

[출력]
각 테스트 케이스마다 N일 동안의 동아리 활동을 할 수 있는 경우의 수를 출력하는 프로그램을 작성하라.

이 수는 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력

2 BC ADCBBACDCBCBACBDCABDCBA

출력

#1 29 #2 88253169

---

접근 방식

비트마스킹 + DP를 공부하기 위한 문제...

하지만 둘 다 어려워서 힘들었다.

핵심 키워드 

키를 가진 사람이 이전 날에서 한명은 무조건 필요로하다.

=> and 연산을 했을 때 전 날에 값과 오늘 값을 비교해서 0이 나오면 같은 사람이 한 명도 없는 것으로 판단

 N일 동안 각 날마다 활동의 책임자가 있어서 이 책임자는 무조건 활동에 참여해야 한다.

=> 위에 키워드를 만족하면서 해당 키워드까지 만족해야한다.

어떤 부원이 참여하는지의 경우의 수는 하루에 총 15가지

=> 동아리원 4명이 돌아가면서 나올 수 있는 날짜를 모두 구해야하니 1~15까지를 비트 연산으로 비교하면 쉽게 가능하다.

 

---

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= T; testCase++) {
            String input = br.readLine(); // 책임자 날짜 별로
            int size = input.length();  // 지속해야하는 날짜
            int[][] dp = new int[size][16];
            // 입력 완료
            //// dp 첫날 세팅
            for (int i = 0; i < 16; i++) {
                // 1과 and 연산해서 0이 아니면 가능하니까 dp 값 1로 넣기
                // 책임자가 참여했는지 확인하기
                // A도 참여하고 책임자도 참여했으면 dp에 값 넣음
                if ((i & 1) != 0 && (i & (1 << input.charAt(0) - 'A')) != 0) {
                    dp[0][i] = 1;
                }
            }
            ///// 반복 돌면서 시작하기
            for (int i = 1; i < size; i++) {
                // i일 책임자
                int manager = 1 << (input.charAt(i) - 'A');
                //15가지 경우의 수 비교
                // 어제 => j
                for (int j = 1; j < 16; j++) {
                    // 오늘 => k
                    for (int k = 1; k < 16; k++) {
                        // 오늘 온 사람중 담당자 있는지 확인 && 어제 날자랑 오늘 비트연산으로 겹치는 사람 하나라도 있나 확인
                        if ((k & manager) != 0 && (j & k) != 0) {
                            dp[i][k] += dp[i-1][j];
                            dp[i][k] %= 1_000_000_007;
                        }
                    }
                }
            }
            int res = 0;
            for (int i = 1; i < 16; i++) {
                res += dp[size-1][i];
                res %= 1_000_000_007;
            }
            System.out.println("#" + testCase + " " + res);
        }
    }
}