Q. 3316 자바 : 동아리실 관리하기(D4)

 

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

 

D4 난이도의 문제이고, DP, 메모제이션을 이용한 문제이다.

최근에 DP 알고리즘을 공부중이긴 하지만,

문제를 보고 A, B, C, D를 비트로 변경해서 저장하는 방법까지는 접근을 했지만

이후 꽤 오랜 시간동안 고민했지만 푸는 방법을 모르겠어서

다른분들의 코드를 참고해서 내 방식으로 바꿔서 풀었다.

 

먼저 A, B, C, D의 포함 여부를 4개의 비트로 쪼개서 생각한다.

만약 A만 동아리 활동에 참여할 경우 0001(2),

D와 A가 참여할 경우 1001(2) = 9(10)으로 생각하면 된다.

이런식으로 데이터를 다룬다고 생각한 다음 

이 문제를 푸는데 가장 중요한 내용은 for문 내부에 있는 if문이라고 생각한다.

if ((i & admin) != 0 && (i & 1) != 0) {
    dp[day][i] = 1;
}

day가 0일 때 처음 열쇠는 A가 가지고 또한 활동의 책임자도 포함되어야 하므로

A와 책임자가 모두 포함된 내용들을 dp[0][1~15]에 넣는다.

이 때 배열의 첫 번째 값(0)은 날짜, 두 번째 값은 그 날 나올 수 있는 동아리원(1~15)를 의미한다.

1 ~ 15 (10) = 0001 ~ 1111(2)이므로 동아리원이 해당하는 날짜에 나올수 있는 모든 경우의 수를 표현할 수 있다.

 

이후 dp[1]부터는 이전 조건을 만족하는 동아리원(dp[0][1~15]중 0이아닌 배열)을 가져온 뒤

다음 날의 조건을 충족하는지 계산한다. 그 내용이 아래 조건식이다.(admin은 해당 날짜의 책임자)

if (dp[day-1][i] != 0) {
        for (int j=1; j<16; j++) {
            if ((i & j) != 0 && (j & admin) != 0) {
                dp[day][j] += dp[day-1][i];
                dp[day][j] %= 1000000007;
            }
        }
    }

위 내용들을 합치면 아래와 같은 코드를 작성할 수 있다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Solution
{
    public static void main(String args[]) throws Exception
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            sb.append('#').append(test_case).append(' ');
            char[] schoolChar = br.readLine().toCharArray();
            int[][] dp = new int[10001][16];
            int result = 0;

            for (int day=0; day<schoolChar.length; day++) {
                int admin = 1 << (schoolChar[day] - 'A');
                for (int i=1; i<16; i++) {
                    if (day == 0) {
                        if ((i & admin) != 0 && (i & 1) != 0) {
                            dp[day][i] = 1;
                        }
                        continue;
                    }
                    if (dp[day-1][i] != 0) {
                        for (int j=1; j<16; j++) {
                            if ((i & j) != 0 && (j & admin) != 0) {
                                dp[day][j] += dp[day-1][i];
                                dp[day][j] %= 1000000007;
                            }
                        }
                    }
                }
            }
            for (int i=1; i<16; i++) {
                result += dp[schoolChar.length-1][i];
                result %= 1000000007;
            }
            sb.append(result).append('\n');
        }
        System.out.println(sb);
    }
}