D. Ilya and Escalator

DP, Posibility


출처: Codeforces D. Ilya and Escalator

SOL)
dp[c][i] = c명의 사람 i 시간으로 2차원 dp를 잡고 한다.
ex) dp[1][2] 2초가 지나고 1명이 있는 확률

dp[c+1][i] += dp[c][i-1] *p
dp[c][i] += dp[c][i-1] *(1- p)

c는 0부터 n보다 작을 때까지 면서 i보다 작을 때까지
에스컬레이터는 i시간지나야 i명까지 태울 수 있기 때문이다.

dp[c+1][i] += dp[c][i-1] *p인데 c가 1증가하면
탑승하지 않은 경우도 더해준다.

한번에 더하지 않는 이유는 사람이 1명 뿐일때
1명을 태웠으면 더이상 그 곳에서 파생되는 경우의 수는
고려하면 안되는데 고려해버리는 문제가 발생한다.


[-] Collapse

#include<stdio.h>

int n, t;
double p;
double dp[2010][2010];

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %lf %d", &n, &p, &t);

    dp[0][1] = (1. - p), dp[1][1] = p;
    for (int i = 2; i <= t; i++){
        for (int c = 0; c < i && c < n; c++){
            dp[c + 1][i] += dp[c][i - 1] * p;
            dp[c][i] += dp[c][i - 1] * (1. - p);
        }
    }
    double ans = 0;
    for (int i = 1; i < t; i++) ans += dp[n][i] * n; //이전에 다참
    for (int c = 0; c <= n; c++) ans += dp[c][t] * c; //t까지 봤을 때

    printf("%lf", ans);
    return 0;
}