좌표 이동 경우의 수 구하기
기본 nCr 문제이다.
S |
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
|
|
|
|
|
|
E |
N x M 의 경우 이며,
이동시 경유지점 혹은 도착지점의 경우의 수를 구하면 된다.
이동은 왼쪽 > , 아래 V 로 만 이동 가능하다.
- 직항 : 출발 (S) > 도착(E)은 출발 점의 수 부터 nCr
- 경유 : (출발(S) > 경유(A)) 의 수 x (경유(A) > 도착(E)) 의 수 nCr1 x nCr2
[공식]
일반 코드
n C r = (n-1)C(r-1) + (n-1)C(r) |
DP code
static int binomial(int n, int k) { if(BI[n][k]>0){ return BI[n][k]; } else if(k==0 || n==k){ return BI[n][k] = 1; } else return BI[n][k] = (binomial(n-1, k-1) + binomial(n-1, k)) % MOD; } |