14552번: Mahjong

https://www.acmicpc.net/problem/14552

$O(...)$

x삭이 대기패인지는 다음 경우들을 조사해서 알 수 있다.
1. x삭이 이미 4개면 불가능하다.
2. x삭을 포함해 같은 삭 쌍이 7개인지 조사(같은 패로 두 쌍은 제외)
3. x삭을 포함해 머리 1개 몸통 4개를 만들 수 있는지 조사

2번은 간단히 for-loop를 통해 확인할 수 있다.

3번은 각 숫자 패마다 머리로 가정하고 몸통 4개가 가능한지 그리디 알고리즘으로 따져볼 수 있다.
기존 패에서 x삭을 추가, 머리로 가정한 한 쌍의 패를 제거한 세트가 주어졌다고 하자.
작은 i부터 보며
i-2, i-1, i번 패가 모두 한 장이상 존재하면 이들로 가능한 만큼의 몸통을 만들고
이후 i번 패가 세 장 이상 존재하면 이들로 몸통을 만든다.
이렇게 해서 만든 몸통이 4개면 x삭은 대기패이다.

#include<cstdio>
int c[10], ck;
bool f() {
    int cnt = 0;
    for (int j = 1; j <= 9; j++) if (c[j] == 2) cnt++;
    if (cnt == 7) return true;
    for (int j = 1; j <= 9; j++) if (c[j] > 1) {
        int t[10], cnt = 0;
        for (int k = 1; k <= 9; k++) t[k] = c[k];
        t[j] -= 2;
        for (int k = 1; k <= 9; k++) {
            while (k > 2 && t[k - 2] && t[k - 1] && t[k]) t[k - 2]--, t[k - 1]--, t[k]--, cnt++;
            if (t[k] > 2) t[k] -= 3, cnt++;
        }
        if (cnt == 4) return true;
    }
    return false;
}
int main() {
    for (int i = 1, x; i <= 13; i++) scanf("%d", &x), c[x]++;
    for (int i = 1; i <= 9; i++) if (c[i] < 4) {
        c[i]++;
        if (f()) printf("%d ", i), ck = 1;
        c[i]--;
    }
    if (!ck) puts("-1");
    return 0;
}