Expectation

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28693 🧐 관찰 및 접근 # 문제 상황을 잘 생각해보자. $N$종류의 카드 $2N$개가 있다고 하자. 처음에 고른 두 카드가 같은 쌍이라면, $N-1$ 종류의 카드 $2(N-1)$개가 있는 문제로 바꿀 수 있다. 이 확률은 $\frac{1}{2N-1}$이다. 처음에 고른 두 카드가 다른 쌍이라면, 2번의 기회를 더 써서 (총 3번의 기회로) $N-2$종류의 카드 $2(N-2)$개가 있는 문제로 바꿀 수 있다. 이 확률은 $\frac{2N-2}{2N-1}$이다. …인줄 알았는데 아니다! 생각해보니 $N \geq 3$일때 두개를 깐다고 해서 나머지의 위치를 모른다.. 그렇다면 DP식을 새롭게 세워보자. $DP[N][K]$ : $N$ 쌍의 안깐 카드, $K$종의 위치를 아는 카드가 있을 때의 기댓값 언제나 안깐 카드를 먼저 까는게 최적인데, 그렇다면 $\frac{K}{2N+K}$의 확률로 이미 위치를 아는 카드를 발견하거나 $\frac{2N}{2N+K}$의 확률로 안깐카드를 발견하는데, 이때 $\frac{1}{2N+K-1}$의 확률로 한방에 맞추거나 $\frac{K}{2N+K-1}$의 확률로 원래 알던 쌍이 나와서, 다음 턴에 그걸 맞추거나 $\frac{2N-2}{2N+K-1}$의 확률로 새로운 쌍이 나와서 $K$가 2 늘어나거나 와 같은 식으로 정리된다. 💻 풀이 # 코드 (C++): mint calc(int N, int K){ // $DP[N][K]$ : $N$ 쌍의 안깐 카드, $K$종의 위치를 아는 카드가 있을 때의 기댓값 if(N < 0 || K < 0) return 0; if(N == 0) return mint(K); if(visited[N][K]) return DP[N][K]; visited[N][K] = true; mint res = 0; // 위치를 아는 카드를 뽑는 경우 res += (mint(K) / mint(2*N+K)) * (calc(N, K-1) + 1); // 위치를 모르는 카드를 뽑는 경우 // 두번째 카드가 첫번째 뽑은 카드와 맞는 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(1) / mint(2*N+K-1)) * (calc(N-1, K) + 1); // 두번째 카드가 이미 위치를 아는 카드와 맞는 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(K) / mint(2*N+K-1)) * (calc(N-1, K) + 2); // 두번째 카드가 아예 새로운 카드일 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(2*N-2) / mint(2*N+K-1)) * (calc(N-2, K+2) + 1); return DP[N][K] = res; } void solve(){ int N; cin >> N; cout << calc(N, 0); } 🔒 구현 코드 잠금