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은 허용 메모리를 초과하기 때문에 이 문제에선 이렇게 접근하면 안된다.