백준 33044 c++ 문제풀이

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> original_count(9, 0);
unordered_map<long long, bool> memo;

long long get_key(const vector<int>& counts) {
    long long key = 0;
    for (int i = 0; i < 9; ++i) {
        key = key * 5 + counts[i];
    }
    return key;
}

bool backtrack(vector<int>& counts, int formed) {
    if (formed == 4) return true;

    // 커쯔 확인
    for (int i = 0; i < 9; ++i) {
        if (counts[i] >= 3) {
            counts[i] -= 3;
            if (backtrack(counts, formed + 1)) {
				// 커쯔를 만들 수 있으면 끝
                counts[i] += 3;
                return true;
            }
            counts[i] += 3;
        }
    }

    // 슌쯔 확인
    for (int i = 0; i <= 6; ++i) {  // i, i+1, i+2
        if (counts[i] >= 1 && counts[i + 1] >= 1 && counts[i + 2] >= 1) {
            counts[i]--;
            counts[i + 1]--;
            counts[i + 2]--;
            if (backtrack(counts, formed + 1)) {
                counts[i]++;
                counts[i + 1]++;
                counts[i + 2]++;
                return true;
            }
            counts[i]++;
            counts[i + 1]++;
            counts[i + 2]++;
        }
    }

    return false;
}

bool can_form_mentsu(vector<int> counts) {
    long long key = get_key(counts);
	auto it = memo.find(key); // 메모이제이션
	if (it != memo.end()) { // 이미 계산한 경우
        return it->second;
    }
    bool result = backtrack(counts, 0);
    memo[key] = result;
    return result;
}

int comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k == 1) return n;
    if (n == 4) {
        if (k == 2) return 6;
        if (k == 3) return 4;
    }
    if (n == 3) {
        if (k == 2) return 3;
    }
    return 0;
}

void generate_c(int idx, int sum, vector<int>& current, long long& total) {
	if (idx == 9) {
        if (sum != 14) return;

        // 치또이쯔 ㄱㄴ?
        int head7 = 0;
        bool is_head7 = true;
        for (int i = 0; i < 9; ++i) {
            if (current[i] != 0 && current[i] != 2) {
                is_head7 = false;
                break;
            }
            if (current[i] == 2) head7++;
        }
        if (is_head7 && head7 == 7) {
            long long product = 1;
            for (int i = 0; i < 9; ++i) {
                product *= comb(original_count[i], current[i]);
            }
            total += product;
            return;
        }

        // 그냥 일반 화료조건
        for (int x = 0; x < 9; ++x) {
            if (current[x] < 2) continue;
            vector<int> new_counts(current);
            new_counts[x] -= 2;
            bool ok = true;
            for (int i = 0; i < 9; ++i) {
                if (new_counts[i] < 0 || new_counts[i] > 4) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            if (can_form_mentsu(new_counts)) {
                long long product = 1;
                for (int i = 0; i < 9; ++i) {
                    product *= comb(original_count[i], current[i]);
                }
                total += product;
                return;
            }
        }

        return;
    }

    int max_possible = min(original_count[idx], 4);
    for (int k = 0; k <= max_possible; ++k) {
        if (sum + k > 14) continue;
        current.push_back(k);
        generate_c(idx + 1, sum + k, current, total);
        current.pop_back();
    }
}

int main() {
    int N;
    cin >> N;

    original_count.assign(9, 0);
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        original_count[a - 1]++;
    }

    long long total = 0;
    vector<int> current;
    generate_c(0, 0, current, total);

    cout << total << endl;

    return 0;
}

용어가 익숙하지 않거나 하면 난이도(골드 1)에 비해 더 어렵게 느껴질 수 있다고 생각한다...
개인적으로는 마작 좋아하는 편이라 재밌게 품