Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

3316. 동아리실 관리하기

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • Day 2 주제가 비트 연산이었던 것이 큰 힌트가 되었다. 각 날짜별 동아리원 참석 여부는 비트 마스킹으로 비교하였다.
  • 첫 번째 날 A가 열쇠를 들고있다는 사실을 몰라서 한참을 헤매었다. → 문제를 꼼꼼히 읽을 것.
  • 첫 풀이 시도에서는 분할정복, 완전탐색 문제로서 접근했는데, 제한된 시・공간 복잡도를 만족시키지 못하였다.
    • $O(15^N)$의 시간 복잡도로 TLE.
    • memoization을 통한 성능 개선을 시도했으나, stack 메모리 영역 사용량이 최대 2MB로 MLE (RE).
  • DP를 사용하는 $O(N)$인 새로운 풀이 방식을 떠올리고 처음부터 다시 구현하여 한 번에 통과.
    • $i$번째 날에 어떠한 동아리원 조합으로 활동이 가능한지 여부는 $i-1$번째 날 동아리원 조합과(곂치는 부원이 있는지), 담당자의 출석여부로만 결정된다는 것이 포인트.
    • 어떤 임의의 날에 조합 가능한 동아리원의 경우의 수는 최대 $15$개이다. (아무도 안나오는 경우를 제외하여 $2^4-1$)
    • $i=1…n$ 번째 날까지 순차적으로 계산해 나아간다면, $O(15^2n)$의 시간에 모든 날짜별 활동 가능한 경우의 수를 구할 수 있음.
#include <array>
#include <iostream>
#include <numeric>

#define MOD 1000000007

using namespace std;

void swapArray(array<int, 16>* x, array<int, 16>* y) {
    array<int, 16> z;
    z = *x;
    *x = *y;
    *y = z;
}

int solveTestCase(string assignees) {
    int answer;
    unsigned int day;
    unsigned char assignee;
    unsigned char member;
    unsigned char lastMember;
    array<int, 16> members;
    array<int, 16> lastMembers;
    lastMembers.fill(0);
    lastMembers.at(0b0001) = 1;
    for (day = 0; day < assignees.length(); day++) {
        assignee = 1 << (assignees.at(day) - 'A');
        members.fill(0);
        for (member = 0b0001; member <= 0b1111; member++) {
            for (lastMember = 0b0001; lastMember <= 0b1111; lastMember++) {
                if ((member & assignee) == 0 || (member & lastMember) == 0) {
                    continue;
                }
                members.at(member) += lastMembers.at(lastMember);
                members.at(member) %= MOD;
            }
        }
        swapArray(&lastMembers, &members);
    }
    answer = 0;
    for (int member = 0b0001; member <= 0b1111; member++) {
        answer += lastMembers.at(member);
        answer %= MOD;
    }
    return answer;
}

void solve() {
    int N;
    string assignees;
    cin >> N;
    for (int testCaseNo = 1; testCaseNo <= N; testCaseNo++) {
        cin >> assignees;
        cout << '#' << testCaseNo << ' ' << solveTestCase(assignees) << '\n';
    }
    return;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("sample_input.txt", "r", stdin);
    // freopen("sample_output.txt", "w", stdout);
    solve();
    return 0;
}

Back to top