[Baekjoon - 15850] Random Number Generator

난이도: Platinum IV

 

태그

• Dynamic Programming → Expected Value
• Probability Theory

 

풀이

1. 2번 더 나와야 하는 수가 \( a \)개 있고, 1번 더 나와야 하는 수가 \( b \)개 있을 때의 기댓값은?

\( dp_{a, b} \) = 2번 더 나와야 하는 수가 \( a \)개 있고, 1번 더 나와야 하는 수가 \( b \)개 있을 때의 기댓값 을 정의해봅시다.

 

초항은 \( dp_{0, 0} = 0 \)입니다.

점화식은, 랜덤한 수를 뽑았을 때 나올 수 있는 3가지 경우로 나눠봅시다.

• 2번 더 나와야 하는 \( a \)개 중 하나일 때: \( dp_{a-1, b+1} + 1 \)
• 1번 더 나와야 하는 \( b \)개 중 하나일 때: \( dp_{a, b-1} + 1 \)
• 이미 충분히 나온 \( n-a-b \)개 중 하나일 때: \( dp_{a, b} + 1 \)

 

이를 식으로 적어보면, \( dp_{a, b} = \frac{a}{n}(dp_{a-1, b+1} + 1) + \frac{b}{n}(dp_{a, b-1} + 1) + \frac{n-a-b}{n}(dp_{a, b} + 1) \)이 됩니다.

 

이제 안에 있는 1을 다 바깥으로 꺼내고, \( dp_{a, b} \)를 우측으로 모아줍시다.

\( \left( 1 - \frac{n-a-b}{n} \right) dp_{a, b} = \frac{a}{n}dp_{a-1, b+1} + \frac{b}{n}dp_{a, b-1} + \frac{a}{n} + \frac{b}{n} + \frac{n-a-b}{n} \)

 

\( 1 - \frac{n-a-b}{n} = \frac{a+b}{n} \)으로 고치고, \( \frac{a}{n} + \frac{b}{n} + \frac{n-a-b}{n} = 1 \)로 고친 뒤, 양변에 \( n \)를 곱해봅시다.

\( (a+b) dp_{a, b} = a \cdot dp_{a-1, b+1} + b \cdot dp_{a, b-1} + n \)

 

마지막으로 양변을 \( a+b \)로 나눠봅시다.

\( dp_{a, b} = \frac{a \cdot dp_{a-1, b+1} + b \cdot dp_{a, b-1} + n}{a+b} \)

 

이제 적당한 점화식이 나오긴 했는데...

\( a, b, n \) 3개의 변수에 의해 조작되므로 \( O(N^3) \)의 시간이 걸리게 됩니다.

이걸 좀 더 빠르게 실행해볼 수 없을까요?

 

2. 점화식의 특징은?

점화식을 잘 생각해보면, 선형 점화식입니다.

그러므로, \( dp_{a, b} \)의 값은 적절한 실수 \( c \)에 대해 \( c \cdot n \)으로 나타낼 수 있지 않을까 하는 의심을 해볼 수 있습니다.

 

초항인 \( dp_{0, 0} = 0 = 0 \cdot n \)이므로, 초항에 대해서는 잘 성립합니다.

이제, 점화식을 확인해봅시다.

 

\( c_1 \cdot n = dp_{a-1, b+1} \), \( c_2 \cdot n = dp_{a, b-1} \)라고 하면, 점화식은

\( dp_{a, b} = \frac{a \cdot dp_{a-1, b+1} + b \cdot dp_{a, b-1} + n}{a+b} = \frac{a c_1 n + b c_2 n + n}{a+b} = \frac{a c_1 + b c_2 + 1}{a+b} n \)이므로,

역시 적당한 실수값에 \( n \)을 곱한 형태가 나오게 됩니다.

// 잘 생각해보면 그냥 수학적 귀납법입니다.

 

그러니, \( dp_{a, b} \)의 값은 \( n \) 앞에 곱해지는 실수값만 저장하고,

문제의 답을 출력할 때는 \( dp_{a, b} \times n \)을 출력하면 됩니다.

 

3. 주의사항

의도된 바인지는 모르겠지만, \( K \)의 합 제한은 있는데 \( N \)의 합 제한이 없습니다.

\( NT \) 시간에 count 배열 초기화하는 게 무섭다면, 아래 코드처럼 짜세요.

 

4. 코드

const int N = 3000;
ld dp[3020][3020];
 
int arr[100020];
int cnt[3020];
 
void Main(){
    for (int a = 0; a <= N; a++){
        for (int b = 0; a+b <= N; b++){
            if (a==0 && b==0){ dp[a][b] = 0; }
            else{
                ld x = (a==0 ? 0 : dp[a-1][b+1]);
                ld y = (b==0 ? 0 : dp[a][b-1]);
                dp[a][b] = (a*x + b*y + 1) / (a+b);
            }
            //if (a <= 3 && b <= 3){ cout << "DP " << a << ' ' << b << " = " << dp[a][b] << endl; }
        }
    }
    int t; cin >> t; while (t--){
        int n, k; cin >> n >> k;
        int c0 = n, c1 = 0;
        for (int i = 1; i <= k; i++){
            int x; cin >> x; arr[i] = x;
            if (cnt[x] == 0){ c0 -= 1; c1 += 1; }
            if (cnt[x] == 1){ c1 -= 1; }
            cnt[x] += 1;
        }
        cout << dp[c0][c1]*n << endl;
        for (int i = 1; i <= k; i++){ cnt[ arr[i] ] = 0; }
    }
}