[Medium] PerfectMemory

2차원 퍼즐판에서 카드를 뒤집느니 어쩌니 하지만, 사실 퍼즐판이란건 아무 의미도 없다. 그냥 바구니에 카드가 N쌍이 담겨있다고 생각하면 좀 쉬워진다. 플레이어는 여태까지 뒤집어서 확인한 모든 카드를 기억한다고 했고, 최소의 기대값이 나오도록 플레이 한다고 했으므로 만약 어떤 카드쌍의 위치를 둘 다 알고 있다면 바로 뒤집어 없애버릴 것이다. 따라서 임의의 순간의 상태는 두장 다 위치를 모르는 쌍이 N쌍, 한장만 위치를 아는 쌍이 M쌍 으로 나타낼 수 있다. 위의 상태에서 퍼즐을 완료할 때 까지 걸리는 move의 기댓값을 F(N, M) 이라 하자. 그렇다면 일단 자명하게 F(0, M) = M 맨 처음 뒤집는 카드는 위치를 모르는 카드여야 이득이다. 위치를 모르는 카드는 총 2N+M 장 있다. 카드를 뒤집는 경우는 딱 세가지다. 1) 처음 고른 카드가 M쌍에 속함. 대응되는 카드의 위치를 이미 알고 있으므로 걔를 바로 맞춰서 없애버리면 된다. M/(2N+M) * (F(N, M-1) + 1) 2) 처음 고른 카드가 N쌍에 속함. 두번째 고른 카드가 M쌍에 속함. 맨 처음 고른 카드는 위치를 기억함. 둘이 쌍이 맞지 않으므로 다시 도로 뒤집고 그 다음에 두번째 고른 카드는 이제 쌍을 맞출 수 있으므로 바로 맞춰버린다. 2N/(2N+M) * M/(2N+M-1) * (F(N-1, M) + 2) 3) 첫번째 두번째 고른 카드 모두 N쌍에 속함. 근데 둘이 같은 카드임. 빙고! 바로 맞춰 없애버린다! 2N/(2N+M) * (2N-1)/(2N+M-1) * 1/(2N-1) * (F(N-1, M) + 1) 4) 첫번째 두번째 고른 카드 모두 N쌍에 속함. 근데 둘이 다른 카드임. 두 장 다 위치를 기억하고 도로 뒤집고 다음 기회를 노린다. 2N/(2N+M) * (2N-1)/(2N+M-1) * (2N-2)/(2N-1) * (F(N-2, M+2) + 1)