📝 문제 정보#
🧐 관찰 및 접근#
- 문제 상황을 잘 생각해보자.
- $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 늘어나거나
- 와 같은 식으로 정리된다.
- $DP[N][K]$ : $N$ 쌍의 안깐 카드, $K$종의 위치를 아는 카드가 있을 때의 기댓값
💻 풀이#
- 코드 (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);
}