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

SW Expert Academy

import java.util.Scanner;

class Solution {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T;
        int[][] dp;
        T = sc.nextInt();
        sc.nextLine();
        for (int test_case = 1; test_case <= T; test_case++) {
            String keys = sc.nextLine();
            dp = new int[keys.length()][16];
            first_day(keys, dp);
            for (int i = 1; i < keys.length(); i++) {
                other_day(keys, dp, i);
            }
            int ans = sol(dp);
            System.out.printf("#%d %d\n", test_case, ans);
        }
    }

    public static void first_day(String keys, int[][] dp) {
        int key = 1 << (keys.charAt(0) - 'A');
        for (int i = 1; i < 16; i++) {
            if ((i & key) != 0 && (i & 1) != 0) dp[0][i] = 1;
        }
    }
    public static void other_day(String keys, int[][] dp, int day) {
        int key = 1 << (keys.charAt(day) - 'A');
        for (int i = 1; i < 16; i++) {
            if (dp[day - 1][i] != 0) {
                for (int j = 1; j < 16; j++) {
                    if ((j & i) != 0 && (j & key) != 0){
                        dp[day][j] += dp[day - 1][i];
                        dp[day][j] %= 1000000007;
                    }
                }
            }
        }
    }
    public static int sol(int[][] dp){
        int sum = 0;
        for (int i = 1; i < 16; i++){
            sum += dp[dp.length-1][i];
            sum %= 1000000007;
        }
        return sum;
    }
}

1. 어려웠던 점:

- 비트 마스킹을 이런 식으로 이용한다는 점 자체가 너무 헷갈렸다.

- 비트 마스킹을 여러 개 사용하는 것

 

2. 알게된 점:

- 비트 마스킹을 통한 문제풀이 공부

 

3. 알고리즘 풀이:

첫째 날의 조건: A가 키를 들고 참석, 책임자 한 명 참석

다른 날의 조건: 전날 인원이 최소 한 명 겹치고, 책임자 한 명 참석

 

dp[16]은 0000을 제외한 나머지 경우의 수다.

각 자리는 A,B,C,D의 참석여부를 뜻한다.

즉 1011이라면 A,C,D가 참석했다는 뜻.

 

dp[16][day]의 day는 날짜를 뜻한다.

편의상 0일부터 시작으로 친다.

 

위 조건을 조합하면 다소 헷갈리지만 문제 풀이에 접근할 수 있을 것이다.