BOJ 5580 빙고 게임

* BOJ 5580 빙고 게임

[분류 : 다이나믹 프로그래밍]

[풀이]

  똑같은 빙고라는 의미는 어떤 수열을 나열하여 빙고에 체크할 때 의미가 같으면 안된다는 소리. 따라서 행과 열을 뒤집은 빙고판은 의미적으로 같게 된다.

  결국 문제는 집합 {A| 1 <= A <= M} 에서 중복없이 수 N^2개를 합이 S가 되도록 뽑는 경우의 수가 답이 된다.

  차례로 사용할 수 있는 수 한계를 하나씩 늘려나가는 방식을 생각해보자.

  수 k를 사용한다고 가정하면 i번째 사람은 i-1번째 사람까지의 합에서 k를 더한 것으로 생각할 수 있다. 

  여기서 중요한 점은 {A| 1 <= A <= k-1}에 있는 수로만 i-1번째 사람까지의 합을 구성해야한다는 점이다. 이는 차례로 사용할 수 있는 수 한계를 증가시키면서 해결된다.

  그렇기에 인원수 내림차순으로 접근하며 dp를 구성해야 한다(동전 교환 문제를 생각해자). 즉 수 k를 사용하기 위해서는 N^2인원수부터 적용해야하며 차례로 N^2-1, N^2-2, ..., 1 인원일 때까지 적용해야 메모리를 아끼면서 계산할 수 있다.

※ 상태도를 (p, k, s)로 p는 현재 사용한 수의 개수, k는 p개를 고르는 동안 수의 최대값, s는 앞으로 구성해야할 수의 합으로 두고 {A| k+1 <= A <= M}에서 하나(k`)를 고른 다음 (p+1, k`, s - k`) 상태를 갖도록 재귀적으로 진행하는 방식을 생각해볼 순 있다. 하지만 이렇게 dp를 구성하면 3차원으로 구성되고, 각각의 최대값은 49 * 2000 * 3000은 허용 메모리를 초과하기 때문에 이 문제에선 이렇게 접근하면 안된다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 7, MAX_S = 3001, MOD = 1e5;
int main() {
    int N, S, N2, M, dp[50][MAX_S] = {}, i, j, k;
    scanf("%d%d%d", &N, &M, &S);
    N2 = N * N;
    dp[0][0] = 1;
    for (k = 1; k <= M; k++) {
        for (i = N2; i; i--) {
            for (j = k; j <= S; j++)
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD;
        }
    }
    printf("%d", dp[N2][S]);
    return 0;
}