3316. 동아리실 관리하기

링크

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

SW Expert Academy

 

분류

캐싱

비트연산

재귀

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

다음날 동아리 출근여부를 1, 0으로 표현한다고 했을 때

인원이 4명으로 제한되어있으므로 동아리 출근여부는 0000 ~ 1111 로 표현 가능하다.

동아리 열쇠 소지자도 마찬가지로 이진수로 표현하면

비트 연산을 통해 답을 구할 수 있다.

 

시행착오

없음

 

코드

#include<iostream>

using namespace std;

string str;
int len;
int** cache;

int c2i(int i) {
    char c = str[i];

    if (c == 'A') return 8;
    if (c == 'B') return 4;
    if (c == 'C') return 2;
    return 1;
}

int solve(int i, int key) {
    if (cache[i][key] > 0) return cache[i][key];
    if (i >= len) return 0;

    int must = c2i(i), result = 0;

    for (int j = 1; j <= 16; j++) {
        if ((must & j) > 0 && (key & j) > 0) {

            if (i == len - 1) result++;
            else result = (result + solve(i + 1, j)) % 1000000007;
        }
    }

    cache[i][key] = result;
    return result;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> str;
        len = str.size();
        cache = new int* [len + 1];
        for (int i = 0; i <= len; i++) {
            cache[i] = new int[16];
            for (int j = 0; j < 16; j++) cache[i][j] = -1;
        }

        printf("#%d %d\n", test_case, solve(0, 8));
    }

    return 0;
}