BOJ 28243 - 조별 수업
수를 묶을 때, 다음과 같이 생각해보자.
우선 그룹의 크기 $g$를 고정해보자.
$(1)(2,3)(4,5,6,7)$ 처럼 묶는다면 $g=3$ 이고, 항상 앞에 있는 작은 수부터 묶어준다고 생각하면 된다.
마지막에 모든 경우의 수를 따지기 위해 $g!$ 만 곱해주면 된다.
이제 DP를 정의한다.
$dp[i][j][g]=i$가 남은 수중 가장 작은 수이고, $i$ 뒤에 $j$개의 수가 남았고 총 $g$개의 그룹을 만드려 할 때 끝까지 진행했을 때 나오는 경우의 수
$i$를 $n \to 1$ 로 내려가는 것이다.
뒤에서부터 훑으면 앞에서부터 훑는것과 다르게 뒤의 어떤 수들을 고를지 고려할 필요 없이, $i$를 이번 그룹의 최소값으로 쓸거냐 안쓸거냐로만 경우를 나눠줄 수 있기 때문이다.
이제 $j \ge i-1$ 인 경우에는 $i$ 를 최소값으로 쓸 수 있다.
이 때, $i!$ 과 $\dbinom{j}{i-1}$ 를 같이 곱해줘야 한다.
$i$ 개의 수들이 그룹에서 배치될 수 있는 경우의 수와 남은 $j$ 개의 수 들 중에 $i-1$ 개를 뽑는 경우의 수이기 때문이다.
이렇게 $O(n^2\sqrt{ n })$ 정도에 DP테이블을 모두 처리하고 정답을 구할 수 있다.
Comments