BOJ 14949 - 외계 미생물

image.png

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

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

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

Tags:

Categories:

Updated:

Comments

You may also enjoy

thumbnail

iOS, SwiftUI Guide (AI generated)

제가 예전에 공부 내역을 정리한 포스팅을 GPT 4.5 Deep Research로 내용을 정리해달라 한 문서입니다.