BOJ 14949 - 외계 미생물

BOJ 14949 - 외계 미생물

$dp[h][w]=h$ 일이 지났을 때 $w$ 마리인 경우의 수라고 하자.

현재 $w$ 마리가 있을 때 $w'$ 마리가 되려면 $w$ 마리 중 중복을 포함하여 순서에 상관없이 $w'$ 마리를 고르는 경우의 수이므로

$_wH_{w'}$ 이고 이는 $_{w+w'-1}C_{w'}$ 이기 때문에 이항계수를 전처리해 DP식을 채워줄 수 있다.